Cooperation of constraint domains in the TOY system

ABSTRACT

This paper presents a computational model for the cooperation of constraint domains, based on a generic Constraint Functional Logic Programming (CFLP) Scheme and designed to support declarative programming with functions, predicates and the cooperation of different constraint domains equipped with their respective solvers. We have developed an implementation in the CFLP system TOY, supporting an instance of the scheme which enables the cooperation of symbolic Herbrand constraints, finite domain integer constraints, and real arithmetic constraints. We provide a theoretical result and an analysis of benchmarks showing a good performance with respect to the closest related approach we are aware of

REFERENCES

• 1: P. Arenas, A.J. Fernández, A. Gil, F.J. López-Fraguas, M. Rodríguez-Artalejo, and F. Sáenz-Pérez. T OY. A Multiparadigm Declarative Language. Version 2.3.1, 2007. R. Caballero and J. Sánchez (Eds.), Available at http://toy.sourceforge.net.
• 2: Franz Baader , Klaus U. Schulz, On the Combination of Symbolic Constraints, Solution Domains, and Constraint Solvers, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.380-397, September 19-22, 1995
• 3: Franz Baader , Tobias Nipkow, Term rewriting and all that, Cambridge University Press, New York, NY, 1998
• 4: S. Estévez-Martín , A. J. Fernández , T. Hortalá-González , M. Rodríguez-Artalejo , F. Sáenz-Pérez , R. del Vado-Vírseda, A Proposal for the Cooperation of Solvers in Constraint Functional Logic Programming, Electronic Notes in Theoretical Computer Science (ENTCS), 188, p.37-51, July, 2007 [doi>10.1016/j.entcs.2007.05.037]
• 5: S. Estévez Martín , A. J. Fernández , M. T. Hortalá González , M. Rodríguez Artalejo , R. del Vado Vírseda, A Fully Sound Goal Solving Calculus for the Cooperation of Solvers in the CFLP Scheme, Electronic Notes in Theoretical Computer Science (ENTCS), 177, p.235-252, June, 2007 [doi>10.1016/j.entcs.2007.01.026]
• 6: Stephan Frank, Petra Hofstedt, and Pierre R. Mai. A flexible metasolver framework for constraint solver collaboration. In Proc. KI 2003, volume 2821 of LNCS, pages 520--534. Springer, 2003.
• 7: Juan Carlos González-Moreno, Maria Teresa Hortalá-González, and Mario Rodríguez-Artalejo. Polymorphic types in functional logic programming. Journal of Functional and Logic Programming, 2001 (1):1--71, 2001.
• 8: L. Granvilliers, E. Monfroy, and F. Benhamou. Cooperative solvers in constraint programming: a short introduction. ALP Newsletter, 14 (2), 2001.
• 9: Timothy J. Hickey. The brandeis interval arithmetic constraint solver. Available from http://www.cs.brandeis.edu/~tim/.
• 10: Petra Hofstedt , Peter Pepper, Integration of declarative and constraint programming, Theory and Practice of Logic Programming, v.7 n.1-2, p.93-121, January 2007 [doi>10.1017/S1471068406002833]
• 11: J. Jaffar and M. Maher. Constraint Logic Programming: a Survey. Journal of Logic Programming, 19&20:503--581, 1994.
• 12: Norio Kobayashi, Mircea Marin, and Tetsuo Ida. Collaborative constraint functional logic programming system in an open environment. EICE Transactions on Information and Systems, E86-D(1):63--70, 2003.
• 13: O. Krzikalla. Constraint solver f ür lineare constraints über reellen zahlen. Groβer Beleg, 1997. Technische Universität Dresden.
• 14: F. J. López-Fraguas , M. Rodríguez-Artalejo , Rafael del Vado Vírseda, A lazy narrowing calculus for declarative constraint programming, Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.43-54, August 24-26, 2004, Verona, Italy [doi>10.1145/1013963.1013972]
• 15: Francisco J. López Fraguas , Mario Rodríguez Artalejo , Rafael Del Vírseda, A new generic scheme for functional logic programming with constraints, Higher-Order and Symbolic Computation, v.20 n.1-2, p.73-122, June 2007 [doi>10.1007/s10990-007-9002-4]
• 16: Eric Monfroy and Carlos Castro. A component language for hybrid solver cooperations. In ADVIS'04, volume 3261 of LNCS, pages 192--202. Springer, 2004.
• 17: Greg Nelson , Derek C. Oppen, Simplification by Cooperating Decision Procedures, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.245-257, Oct. 1979 [doi>10.1145/357073.357079]
• 18: SICStus Prolog, 2007. http://www.sics.se/isl/sicstus.
• 19: Peter van Beek. A C library of routines for solving binary constraint satisfaction problems. Available from http://www.ai.uwaterloo.ca/~vanbeek/software/-csplib.tar.gz.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages; Multiparadigm languages
      D.3.3 Language Constructs and Features
          Subjects: Constraints

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
constraint domains and solvers, domain cooperation, functional and logic programming