Abstract
Constraint logic programming emerged in the late 80’s as a highly declarative class of programming languages based on first-order logic and theories with decidable constraint languages, thereby subsuming Prolog restricted to equality constraints over the Herbrand’s term domain. This approach has proven extremely successful in solving combinatorial problems in the industry which quickly led to the development of a variety of constraint solving libraries in standard programming languages. Later came the design of a purely declarative front-end constraint-based modeling language, MiniZinc, independent of the constraint solvers, in order to compare their performances and create model benchmarks. Beyond that purpose, the use of a high-level modeling language such as MiniZinc to develop complete applications, or to teach constraint programming, is limited by the impossibility to program search strategies, or new constraint solvers, in a modeling language, as well as by the absence of an integrated development environment for both levels of constraint-based modeling and constraint solving. In this paper, we propose to solve those issues by taking Prolog with its constraint solving libraries, as a unified relation-based modeling and programming language. We present a Prolog library for high-level constraint-based mathematical modeling, inspired by MiniZinc, using subscripted variables (arrays) in addition to lists and terms, quantifiers and iterators in addition to recursion, together with a patch of constraint libraries in order to allow array functional notations in constraints. We show that this approach does not come with a significant computation time overhead, and presents several advantages in terms of the possibility of focussing on mathematical modeling, getting answer constraints in addition to ground solutions, programming search or constraint solvers if needed, and debugging models within a unique modeling and programming environment.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The Prolog libraries presented here form a pack named modeling, currently available for SWI-Prolog at https://lifeware.inria.fr/wiki/Main/Software#modeling.
References
Apt, K., Wallace, M.: Constraint Logic Programming Using Eclipse. Cambridge University Press, Cambridge (2006)
Coquery, E., Fages, F.: TCLP: overloading, subtyping and parametric polymorphism made practical for CLP. In: Stuckey, P.J. (ed.) ICLP 2002. LNCS, vol. 2401, p. 480. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45619-8_42
Coquery, E., Fages, F.: Subtyping constraints in quasi-lattices. In: Pandya, P.K., Radhakrishnan, J. (eds.) FSTTCS 2003. LNCS, vol. 2914, pp. 136–148. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24597-1_12
Fages, F., Coquery, E.: Typing constraint logic programs. J. Theory Pract. Log. Program. 1(6), 751–777 (2001)
Fages, F., Soliman, S., Coolen, R.: CLPGUI: a generic graphical user interface for constraint logic programming. J. Constraints Spec. Issue User-Interact. Constraint Satisfaction 9(4), 241–262 (2004). https://doi.org/10.1023/B:CONS.0000049203.53383.c1
Frühwirth, T.W.: Constraint Handling Rules. Cambridge University Press, Cambridge (2009)
Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: IJCAI 1995: Proceedings of the 14th International Joint Conference on Artificial Intelligence, pp. 607–613. Morgan Kaufmann Publishers Inc., San Francisco (1995)
Jaffar, J., Lassez, J.L.: Constraint logic programming. In: Proceedings of the 14th ACM Symposium on Principles of Programming Languages, Munich, Germany, pp. 111–119. ACM (1987)
Lassez, J.L., Maher, M.J.: On Fourier’s algorithm for linear arithmetic constraints. J. Autom. Reason. 9, 373–379 (1992)
Martinez, T., Fages, F., Soliman, S.: Search by constraint propagation. In: Proceedings of the 17th International Conference on Principles and Practice of Declarative Programming, PPDP 2015, pp. 173–183. ACM (2015). https://doi.org/10.1145/2790449.2790527
Carlsson, M., et al.: Sicstus 4.2.3 (2012). https://sicstus.sics.se/
Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard CP modelling language. In: Bessiére, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_38
Rendl, A., Guns, T., Stuckey, P.J., Tack, G.: MiniSearch: a solver-independent meta-search language for MiniZinc. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 375–392. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23219-5_27
Sagonas, K., Warren, D.S.: Efficient execution of HiLog in WAM-based prolog implementations. In: Sterling, L. (ed.) Proceedings of the 12th International Conference on Logic Programming, pp. 349–363. MIT Press (1995)
Schrijvers, T., Tack, G., Wuille, P., Samulowitz, H., Stuckey, P.J.: Search combinators. Constraints 18(2), 269–305 (2013)
The Zinc Team: MiniZinc web page (2023). http://www.minizinc.org/
Walsh, T.: General symmetry breaking constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 650–664. Springer, Heidelberg (2006). https://doi.org/10.1007/11889205_46
Warren, D.: An abstract Prolog instruction set. Technical note 309, SRI International, Menlo Park (1983)
Warren, D.H.D.: Higher-order extension to PROLOG: are they needed? In: Machine Intelligence, vol. 10, pp. 441–454 (1982)
Acknowledgments
I am grateful to my students at Ecole Polytechnique for their interest in my courses on Constraint Programming including practical work that evolved over the years from Prolog to MiniZinc and now back to Prolog; to Mathieu Hemery and Sylvain Soliman for their participation in the teaching and fruitful discussions; to Guy-Alain Narboni for his vision of the importance of the Prolog heritage and the organization of the 50th year of Prolog in Paris; to Markus Triska, Ulrich Neumerkel and Christian Jendreiko for their organization of the Scryer Meetup in Dusseldorf; and to the reviewers for their comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Fages, F. (2024). A Constraint-Based Mathematical Modeling Library in Prolog with Answer Constraint Semantics. In: Gibbons, J., Miller, D. (eds) Functional and Logic Programming. FLOPS 2024. Lecture Notes in Computer Science, vol 14659. Springer, Singapore. https://doi.org/10.1007/978-981-97-2300-3_8
Download citation
DOI: https://doi.org/10.1007/978-981-97-2300-3_8
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-2299-0
Online ISBN: 978-981-97-2300-3
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science