6 ms·

Prolog is exceptionally well suited for solving such combinatorial puzzles, and of course also for much tougher tasks like timetabling instances in schools, wor

by triska 5y ago

Prolog is exceptionally well suited for solving such combinatorial puzzles, and of course also for much tougher tasks like timetabling instances in schools, workforce rosters, tournament schedules etc. The key feature that makes Prolog so attractive for such tasks is the availability of constraint solvers that ship with many Prolog systems and which can be used to elegantly express these tasks in terms of relations between integers, Boolean variables, rational numbers and other domains. The sophistication and efficiency of constraint solvers depend heavily on the used Prolog system, and fast constraint solvers are often an important motivation for buying a commercial Prolog system such as SICStus Prolog. Interestingly, constraint solvers can themselves be implemented elegantly and efficiently in Prolog too. See for example A Pearl on SAT Solving in Prolog by Howe and King, where the authors use Prolog and its delay declarations to implement a succinct SAT solver with watched literals and unit propagation: http://www.staff.city.ac.uk/~jacob/solver/flops.pdf http://www.staff.city.ac.uk/~jacob/solver/flops.pdf

TimTheTinker 5y ago
I'm curious how solvers in commercial Prolog systems compare to the family of MiniZinc solvers, like Google's OR-Tools or GECode. There are plenty of examples of Sudoku models in MiniZinc, and models for many other combinatorial problems as well.
- triska 5y ago
  Yes, it is easy to express simple tasks like Sudoku in MiniZinc. However, in terms of sophistication and convenience, Prolog is hard to beat, since it is a full-fledged programming language that can also be used to fetch, process and transform any available input in any way necessary to make it amenable to all built-in constraint solvers. Compared to a Prolog program, a MiniZinc model is quite hard to parse and reason about programmatically: Every Prolog program is also a valid Prolog term, and can be reasoned about logically as long as we keep to the pure monotonic core of Prolog, which also includes constraints. Pure Prolog programs can be debugged declaratively by generalizing away goals, whereas for example removing a line of a MiniZinc model may render the model invalid. In addition, Prolog provides logic variables and therefore allows interesting questions to be asked about the model, such as queries about partially known data. This, in combination with Prolog being a programming language, allows its application in a way that is not readily available, or may not be possible at all, with more special-purpose tools and modeling languages. For instance, David C. Norris is using Scryer Prolog and its integer constraints to model and analyse dose escalation trials as they arise in clinical oncology, exceeding the expressiveness of other modeling languages: https://github.com/dcnorris/precautionary https://github.com/dcnorris/precautionary Regarding sophistication, a good example are dedicated placement constraints of SICStus Prolog such as the geost/N family of constraints: https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/Placement-Constraints.html https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.ht... The publication A Geometric Constraint over k-Dimensional Objects and Shapes Subject to Business Rules by Carlsson, Beldiceanu and Martin gives an overview of what is going on behind the scenes when these constraints are posted: http://contraintes.inria.fr/~jmartin/CBM08cp.pdf http://contraintes.inria.fr/~jmartin/CBM08cp.pdf Implementing these constraints with the efficiency, generality and correctness that SICStus provides is a huge project.
  - jhgb 5y ago
    > However, in terms of sophistication and convenience, Prolog is hard to beat, since it is a full-fledged programming language that can also be used to fetch, process and transform any available input in any way necessary to make it amenable to all built-in constraint solvers. Surely the same thing could be accomplished in Lisp as well?
    - dreamcompiler 5y ago
      Yes but it would take more work. Prolog is tailor-made for solving logic and constraint problems like Sudoku out of the box; Lisp is not. That said, it's relatively easy to write a version of Prolog in Lisp and then just use that to solve the problem. Both pg and Peter Norvig show that in their Lisp books.
    - simplify 5y ago
      It can indeed! Both lisp and prolog are homoiconic :)
    - Tomte 5y ago
      Yes, and commercial Lisp implementations often include a reasonably performant Prolog. If you'd like to see how to do that yourself: https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp
- mzl 5y ago
  The underlying implementation of the main classical part of the solvers are fairly similar. See for example the overview of how to implements such systems by the main authors of SICStus Prolog and Gecode in https://chschulte.github.io/papers/schultecarlsson-cph-2006.html https://chschulte.github.io/papers/schultecarlsson-cph-2006.... . Choosing a solver to solve a specific problem comes down to experience, familiarity, available global constraints, and suitability for the problem and implementation environment at hand. With that said, solvers such as OR-Tools (in their newer CP-SAT engine) and Chuffed are using something called Lazy Clause Generation, which can be very effective for many problems. This is partly a newer way to implements CP solvers that uses a built-in SAT solver as the domain store. I know of no Prolog system that uses this architecture.
alserio 5y ago
I've really liked Prolog during university, but I've never used a constraint solver embedded in Prolog. Do you know of any non commercial Prolog system with this kind of integration to play with? I remember using SWIProlog at the time
- triska 5y ago
  GNU Prolog has one of the fastest constraint solvers over finite domains (i.e., small integers), and its constraints are available out of the box, without loading any library. For example: $ gprolog GNU Prolog 1.4.5 (64 bits) Compiled Mar 24 2020, 20:46:07 with gcc By Daniel Diaz Copyright (C) 1999-2020 Daniel Diaz | ?- X #> 3. X = _#2(4..268435455) yes GNU Prolog 1.5.0 was recently released, and the source repository is now available at: https://github.com/didoudiaz/gprolog https://github.com/didoudiaz/gprolog GNU Prolog is a nice Prolog system for learning Prolog, also because it is currently the only free system that correctly handles all syntactic ISO conformity tests collected at: https://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_testing https://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformi... This means that GNU Prolog can be reliably used to learn what is valid Prolog syntax and what is not.
  - alserio 5y ago
    Thanks!
- jjgreen 5y ago
  SWI is still going strong, the main git repo looks to be consistently merging 3-4 PRs a month.
- oldsecondhand 5y ago
  SWI Prolog also comes with constraint solvers. It has CLP(B) (booleans), CLP(FD)(finite domain), CLP(Q,R) (rationals and reals) and CHR (constraint handling rules). These come as standard libraries, no additional installation needed. If you want to get started, I recommend starting with CLP(FD) as that has a lot of tutorials and is highly compatible between Prolog implementations.
castratikron 5y ago
I've found that a lot of "logic" problems on standardized tests like the LSAT or whatever are really just puzzles that force you to permute through the problem space and apply rules. I was able to do this pretty quickly when I discovered Prolog (very bored during covid). I've become convinced that there is likely at least one person employed in writing these tests that generated these questions with the same technique.
TimTheTinker 5y ago
Is it possible for Prolog to beat OptaPlanner in terms of convenience and usability in a production context? As I understand it, local search and simulated annealing enable constraints to be expressed as arbitrary functions that return a Boolean or integer -- which can be much easier to express and connect to domain models than first-class logical predicates (at the price of a guaranteed optimum solution).
- freemint 5y ago
  Not for planning tasks. Prolog essentially expands a search tree depth first. OptaPlanner can and probably does do better things. Yes you could implement OptaPlanner in Prolog but then you are no longer using the Prolog language facilities.

by triska 5y ago

TimTheTinker 5y ago

I'm curious how solvers in commercial Prolog systems compare to the family of MiniZinc solvers, like Google's OR-Tools or GECode. There are plenty of examples of Sudoku models in MiniZinc, and models for many other combinatorial problems as well.

triska 5y ago
Yes, it is easy to express simple tasks like Sudoku in MiniZinc. However, in terms of sophistication and convenience, Prolog is hard to beat, since it is a full-fledged programming language that can also be used to fetch, process and transform any available input in any way necessary to make it amenable to all built-in constraint solvers. Compared to a Prolog program, a MiniZinc model is quite hard to parse and reason about programmatically: Every Prolog program is also a valid Prolog term, and can be reasoned about logically as long as we keep to the pure monotonic core of Prolog, which also includes constraints. Pure Prolog programs can be debugged declaratively by generalizing away goals, whereas for example removing a line of a MiniZinc model may render the model invalid. In addition, Prolog provides logic variables and therefore allows interesting questions to be asked about the model, such as queries about partially known data. This, in combination with Prolog being a programming language, allows its application in a way that is not readily available, or may not be possible at all, with more special-purpose tools and modeling languages. For instance, David C. Norris is using Scryer Prolog and its integer constraints to model and analyse dose escalation trials as they arise in clinical oncology, exceeding the expressiveness of other modeling languages: https://github.com/dcnorris/precautionary https://github.com/dcnorris/precautionary Regarding sophistication, a good example are dedicated placement constraints of SICStus Prolog such as the geost/N family of constraints: https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/Placement-Constraints.html https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.ht... The publication A Geometric Constraint over k-Dimensional Objects and Shapes Subject to Business Rules by Carlsson, Beldiceanu and Martin gives an overview of what is going on behind the scenes when these constraints are posted: http://contraintes.inria.fr/~jmartin/CBM08cp.pdf http://contraintes.inria.fr/~jmartin/CBM08cp.pdf Implementing these constraints with the efficiency, generality and correctness that SICStus provides is a huge project.
- jhgb 5y ago
  > However, in terms of sophistication and convenience, Prolog is hard to beat, since it is a full-fledged programming language that can also be used to fetch, process and transform any available input in any way necessary to make it amenable to all built-in constraint solvers. Surely the same thing could be accomplished in Lisp as well?
  - dreamcompiler 5y ago
    Yes but it would take more work. Prolog is tailor-made for solving logic and constraint problems like Sudoku out of the box; Lisp is not. That said, it's relatively easy to write a version of Prolog in Lisp and then just use that to solve the problem. Both pg and Peter Norvig show that in their Lisp books.
  - simplify 5y ago
    It can indeed! Both lisp and prolog are homoiconic :)
  - Tomte 5y ago
    Yes, and commercial Lisp implementations often include a reasonably performant Prolog. If you'd like to see how to do that yourself: https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp
mzl 5y ago
The underlying implementation of the main classical part of the solvers are fairly similar. See for example the overview of how to implements such systems by the main authors of SICStus Prolog and Gecode in https://chschulte.github.io/papers/schultecarlsson-cph-2006.html https://chschulte.github.io/papers/schultecarlsson-cph-2006.... . Choosing a solver to solve a specific problem comes down to experience, familiarity, available global constraints, and suitability for the problem and implementation environment at hand. With that said, solvers such as OR-Tools (in their newer CP-SAT engine) and Chuffed are using something called Lazy Clause Generation, which can be very effective for many problems. This is partly a newer way to implements CP solvers that uses a built-in SAT solver as the domain store. I know of no Prolog system that uses this architecture.

alserio 5y ago

I've really liked Prolog during university, but I've never used a constraint solver embedded in Prolog. Do you know of any non commercial Prolog system with this kind of integration to play with? I remember using SWIProlog at the time

triska 5y ago
GNU Prolog has one of the fastest constraint solvers over finite domains (i.e., small integers), and its constraints are available out of the box, without loading any library. For example: $ gprolog GNU Prolog 1.4.5 (64 bits) Compiled Mar 24 2020, 20:46:07 with gcc By Daniel Diaz Copyright (C) 1999-2020 Daniel Diaz | ?- X #> 3. X = _#2(4..268435455) yes GNU Prolog 1.5.0 was recently released, and the source repository is now available at: https://github.com/didoudiaz/gprolog https://github.com/didoudiaz/gprolog GNU Prolog is a nice Prolog system for learning Prolog, also because it is currently the only free system that correctly handles all syntactic ISO conformity tests collected at: https://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_testing https://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformi... This means that GNU Prolog can be reliably used to learn what is valid Prolog syntax and what is not.
- alserio 5y ago
  Thanks!
jjgreen 5y ago
SWI is still going strong, the main git repo looks to be consistently merging 3-4 PRs a month.
oldsecondhand 5y ago
SWI Prolog also comes with constraint solvers. It has CLP(B) (booleans), CLP(FD)(finite domain), CLP(Q,R) (rationals and reals) and CHR (constraint handling rules). These come as standard libraries, no additional installation needed. If you want to get started, I recommend starting with CLP(FD) as that has a lot of tutorials and is highly compatible between Prolog implementations.

castratikron 5y ago

I've found that a lot of "logic" problems on standardized tests like the LSAT or whatever are really just puzzles that force you to permute through the problem space and apply rules. I was able to do this pretty quickly when I discovered Prolog (very bored during covid). I've become convinced that there is likely at least one person employed in writing these tests that generated these questions with the same technique.

TimTheTinker 5y ago

Is it possible for Prolog to beat OptaPlanner in terms of convenience and usability in a production context? As I understand it, local search and simulated annealing enable constraints to be expressed as arbitrary functions that return a Boolean or integer -- which can be much easier to express and connect to domain models than first-class logical predicates (at the price of a guaranteed optimum solution).

freemint 5y ago
Not for planning tasks. Prolog essentially expands a search tree depth first. OptaPlanner can and probably does do better things. Yes you could implement OptaPlanner in Prolog but then you are no longer using the Prolog language facilities.