Comment by zmonx | Hacker News Reader

Comment by zmonx | Hacker News Reader

Parent Full thread

Great! One alternative way to reason about these rules is to recognize that these statements can be modeled as propositional formulas, which can be easily solved with Prolog by using a constraint solver over Boolean variables. For example, in SICStus Prolog, such a constraint solver is available as a library:

https://sicstus.sics.se/sicstus/docs/4.3.1/html/sicstus/CLPB...

This of course requires a slightly different way to encode the task, using logical variables:

    ?- sat(School*Study*Exercise),
       sat(Exercise =< Healthy),
       sat(Study + Sick),
       sat(~Rain),
       sat(Study * ( Gym + Coffee)),
       sat(Rain + (Exercise * Study)),
       sat(Healthy =< (Happy + Fit)).

As an answer, we get:

    School = Study, Study = Exercise, Exercise = Healthy, Healthy = 1,
    Rain = 0,
    sat(Sick=:=Sick),
    sat(Gym=\=Gym*Coffee#Coffee),
    sat(Happy=\=Happy*Fit#Fit).

Since CLP(B) is complete, these are all the consequences that can be derived from the initial knowledge. Note that for example `Gym = 1` is consistent with the initial assumptions, it just doesn't follow from them.

To obtain ground solutions, you can use labeling/1 on the remaining free variables, showing all possible ways in which truth values can be assigned to them.

Very interesting! Do you know how is the constraint solver library implemented? Does it use a different general implementation than the regular prolog statements?

There are several different ways to implement such solvers on top of Prolog.

One way is to simply extend the Prolog engine to handle such constraints natively. Many basic constraints are implemented in this way. In fact, you can regard even (=)/2, i.e., unification, as one such constraint, and all Prolog systems implement it, typically as one of their virtual machine instructions. The same method naturally extends to other constraints like freeze/2 and (in)/2, which are often implemented natively. See the system descriptions of GNU Prolog, as one example for a system that handles the CLP(FD) constraint (in)/2 natively.

For application programmers, Prolog systems typically provide an interface in the form of attributed variables are metastructures, so that any programmer can implement a custom constraint solver on top of Prolog by attaching attributes to variables. For example, in SICStus Prolog, there is a hook called verify_attributes/3, and you can provide a custom user-defined specification that handles your own constraints.

In practice, the implementation of constraint solvers on top of Prolog typically involves a combination of both approaches, with some low-level constraints implemented natively (i.e., as part of the engine), and some higher-level constraints implemented via the general interface on the Prolog level.

There are of course also other ways to do it, such as writing a Prolog meta-interpreter that interprets your code as if the Prolog engine supported such extensions. This is likely among the slower ways to provide such extensions, while a native implementation is among the fastest, and using general interface predicates will likely be somewhere between these extremes.

Reply on news.ycombinator.com