Hacker News Reader

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.

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

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

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/conformi...

This means that GNU Prolog can be reliably used to learn what is valid Prolog syntax and what is not.

Thanks!

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.

Nice. Thank you

SWI is still going strong, the main git repo looks to be consistently merging 3-4 PRs a month.

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.

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

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.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

Implementing these constraints with the efficiency, generality and correctness that SICStus provides is a huge project.

> 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?

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.

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

It can indeed! Both lisp and prolog are homoiconic :)

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.... . 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.

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).

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.