Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Constraint Handling Rules (CHR) is a high-level rule-based programming language which is increasingly used for general-purpose programming. We introduce the CHR machine, a model of computation based on the operational semantics of CHR. Its computational power and time complexity properties are compared to those of the well-understood Turing machine and Random Access Memory machine. This allows us to prove the interesting result that every algorithm can be implemented in CHR with the best known time and space complexity. We also investigate the practical relevance of this result and the constant factors involved. Finally we expand the scope of the discussion to other (declarative) programming languages.

REFERENCES

• 1: Adelson-Velsky, G. M. and Landis, E. M. 1962. An algorithm for the organization of information. Doklady Akademii Nauk SSSR 146, 263--266.
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Boris V. Cherkassky , Andrew V. Goldberg , Tomasz Radzik, Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming: Series A and B, v.73 n.2, p.129-174, May 31, 1996 [doi>10.1007/BF02592101]
• 4: M. Clavel , F. Durán , S. Eker , P. Lincoln , N. Martí-Oliet , J. Meseguer , J. F. Quesada, Maude: specification and programming in rewriting logic, Theoretical Computer Science, v.285 n.2, p.187-243, 28 August 2002 [doi>10.1016/S0304-3975(01)00359-0]
• 5: W F. Clocksin , Christopher S. Mellish, Programming in Prolog (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1984
• 6: De Koninck, L., Schrijvers, T., and Demoen, B. 2007. The correspondence between the Logical Algorithms language and CHR. In Proceedings of the 23rd International Conference on Logic Programming (ICLP'07), V. Dahl and I. Niemelä, Eds. Lecture Notes in Computer Science, vol. 4670. Springer, 209--223.
• 7: Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Math. 1, 4, 269--271.
• 8: Duck, G. J. 2005. Compilation of Constraint Handling Rules. Ph.D. thesis, University of Melbourne, Victoria, Australia.
• 9: Duck, G. J. and Schrijvers, T. 2005. Accurate functional dependency analysis for Constraint Handling Rules. In Proceedings of the 2nd Workshop on Constraint Handling Rules (CHR'05), T. Schrijvers and T. Frühwirth, Eds., 109--124.
• 10: Duck, G. J., Stuckey, P. J., García de la Banda, M., and Holzbaur, C. 2004. The refined operational semantics of Constraint Handling Rules. In Proceedings of the 20th International Conference on Logic Programming (ICLP'04), B. Demoen and V. Lifschitz, Eds. Lecture Notes in Computer Science, vol. 3132, 90--104.
• 11: Duck, G. J., Stuckey, P. J., and Sulzmann, M. 2006. Observable confluence for Constraint Handling Rules. In Proceedings of the 3rd Workshop on Constraint Handling Rules (CHR'06), T. Schrijvers and T. Frühwirth, Eds., 61--76.
• 12: Eker, S. 2003. Associative-Commutative rewriting on large terms. In Proceedings of the Rewriting Techniques and Applications (RTA'03), R. Nieuwenhuis, Ed. Lecture Notes in Computer Science, vol. 2706. Springer, 14--29.
• 13: Forgy, C. L. 1982. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artif. Intell. 19, 1, 17--37.
• 14: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 15: Ernest Friedman Hill, Jess in Action: Java Rule-Based Systems, Manning Publications Co., Greenwich, CT, 2003
• 16: Frühwirth, T. 1992. Constraint simplification rules. Tech. rep. ECRC-92-18, European Computer-Industry Research Centre, Munich, Germany. July.
• 17: Frühwirth, T. 1998. Theory and practice of Constraint Handling Rules. J. Logic Program. 37, 1--3, 95--138.
• 18: Frühwirth, T. 2001. As time goes by II: More automatic complexity analysis of concurrent rule programs. In Proceedings of the Quantitative Aspects of Programming Languages (QAPL'01), A. D. Pierro and H. Wiklicky, Eds. Electronic Notes in Theoretical Computer Science, vol. 59, 3. Elsevier, 185--206.
• 19: Frühwirth, T. 2002. As time goes by: Automatic complexity analysis of concurrent rule programs. In Proceedings of the 8th International Conference on Principles of Knowledge Representation and Reasoning (KR'02), D. Fensel et al., Eds. Morgan Kaufmann, 547--557.
• 20: Fr&uhuml;wirth, T. 2009. Constraint Handling Rules. Cambridge University Press. To appear.
• 21: Thom Fruewirth , Slim Abdennadher, Essentials of Constraint Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 22: Harald Ganzinger , David A. McAllester, Logical Algorithms, Proceedings of the 18th International Conference on Logic Programming, p.209-223, July 29-August 01, 2002
• 23: Joseph C. Giarratano , Gary Riley, Expert Systems: Principles and Programming, PWS Publishing Co., Boston, MA, 1994
• 24: Hartmanis, J. and Stearns, R. E. 1965. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 285--306.
• 25: Holzbaur, C. and Frühwirth, T. 1998. CHR reference manual. Tech. rep. TR-98-01, Österreichisches Forschungsinstitut für Artificial Intelligence, Vienna, Austria.
• 26: Christian Holzbaur , Thom W. Frühwirth, Compiling Constraint Handling Rules into Prolog with Attributed Variables, Proceedings of the International Conference PPDP'99 on Principles and Practice of Declarative Programming, p.117-133, September 29-October 01, 1999
• 27: Christian Holzbaur , Maria Garcia De La Banda , Peter J. Stuckey , Gregory J. Duck, Optimizing compilation of constraint handling rules in HAL, Theory and Practice of Logic Programming, v.5 n.4-5, p.503-531, July 2005 [doi>10.1017/S1471068405002413]
• 28: John E. Hopcroft , Rajeev Motwani , Rotwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 29: Paul Hudak , John Hughes , Simon Peyton Jones , Philip Wadler, A history of Haskell: being lazy with class, Proceedings of the third ACM SIGPLAN conference on History of programming languages, p.12-1-12-55, June 09-10, 2007, San Diego, California [doi>10.1145/1238844.1238856]
• 30: Marriott, K. and Stuckey, P. J. 1998. Programming with Constraints: An Introduction. MIT Press, Cambridge, MA.
• 31: Mazur, N. 2004. Compile-Time garbage collection for the declarative language Mercury. Ph.D. thesis, K. U. Leuven, Leuven, Belgium.
• 32: Miranker, D. P., Brant, D. A., Lofaso, B., and Gadbois, D. 1990. On the performance of lazy matching in production systems. In Proceedings of the 8th National Conference on Artificial Intelligence (AAAI'90), T. Dietterich and W. Swartout, Eds. MIT Press, Boston, MA, 685--692.
• 33: Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
• 34: Okasaki, C. and Gill, A. 1998. Fast mergeable integer maps. In Proceedings of the Workshop on ML, 77--86.
• 35: Savage, J. E. 1998. Models of Computation. Addison-Wesley Longman, Boston, MA.
• 36: Savitch, W. J. 1978. The influence of the machine model on computational complexity. In Interfaces between Computer Science and Operations Research, J. Lenstra et al., Eds. Mathematical Centre Tracts, vol. 99. Centre for Mathematics and Computer Science, Amsterdam, 1--32.
• 37: Schrijvers, T. 2005. Analyses, optimizations and extensions of constraint handling rules. Ph.D. thesis, K. U. Leuven, Leuven, Belgium.
• 38: Schrijvers, T. and Demoen, B. 2004. The K. U. Leuven CHR system: Implementation and application. In Proceedings of the 1st Workshop on Constraint Handling Rules (CHR'04), Selected Contributions, T. Frühwirth and M. Meister, Eds. Ulm, Germany.
• 39: Tom Schrijvers , Thom Frühwirth, Optimal union-find in Constraint Handling Rules, Theory and Practice of Logic Programming, v.6 n.1-2, p.213-224, January 2006 [doi>10.1017/S1471068405002541]
• 40: Jon Sneyers, Turing-Complete Subclasses of CHR, Proceedings of the 24th International Conference on Logic Programming, December 09-13, 2008, Udine, Italy [doi>10.1007/978-3-540-89982-2_72]
• 41: Sneyers, J. and Frühwirth, T. 2008. Generalized CHR machines. In Proceedings of the 5th Workshop on Constraint Handling Rules (CHR'08), T. Schrijvers et al., Eds.
• 42: Sneyers, J., Schrijvers, T., and Demoen, B. 2006a. Dijkstra's algorithm with Fibonacci heaps: An executable description in CHR. In Proceedings of the 20th Workshop on Logic Programming (WLP'06).
• 43: Sneyers, J., Schrijvers, T., and Demoen, B. 2006b. Memory reuse for CHR. In Proceedings of the 22nd International Conference on Logic Programming (ICLP'06), S. Etalle and M. Truszczynski, Eds. Lecture Notes in Computer Science, vol. 4079. Springer, 72--86.
• 44: Sneyers, J., Van Weert, P., De Koninck, L., and Schrijvers, T. 2009. As time goes by: Constraint handling rules—A survey of CHR research between 1998 and 2007. Theory Pract. Logic Program. Submitted.
• 45: Somogyi, Z., Henderson, F., and Conway, T. 1996. The execution algorithm of Mercury, An efficient purely declarative logic programming language. J. Logic Program. 29, 1-3, 17--64.
• 46: Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]
• 47: Turing, A. M. 1936. On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. 2, 42, 230--265.
• 48: Peter van Emde Boas, Machine models and simulations, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 49: Van Weert, P., Schrijvers, T., and Demoen, B. 2005. K. U. Leuven JCHR: A user-friendly, flexible and efficient CHR system for Java. In Proceedings of the 2nd Workshop on Constraint Handling Rules (CHR'05), T. Schrijvers and T. Frühwirth, Eds., 47--62.
• 50: Van Weert, P., Sneyers, J., Schrijvers, T., and Demoen, B. 2006. Extending CHR with negation as absence. In Proceedings of the 3rd Workshop on Constraint Handling Rules (CHR'06), T. Schrijvers and T. Frühwirth, Eds. K. U. Leuven, Department of Computer Science. Venice, Italy, 125--140.
• 51: Wuille, P., Schrijvers, T., and Demoen, B. 2007. CCHR: The fastest CHR implementation, in C. In Proceedings of the 4th Workshop on Constraint Handling Rules (CHR'07), K. Djelloul et al., Eds., 123--137.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Experimentation, Languages, Performance, Theory

Keywords:
Constraint Handling Rules, complexity, constant factors