Conditional doesn't backtrack for solution

[Boris]

One source of endless confusion in programming circles is the unnecessary coupling, in our minds, of an idea (paradigm?) and a concrete tool that attempts to implement that idea. Examples would be functional programming and Haskell; or object-oriented programming and Java; or relational data and SQL. The confusion I have observed comes in at least two flavors:

1. “If you want to do real functional programming you must use Haskell” or
2. “I don’t like SQL so relational databases are crap”

@jan

I have used the term “logical islands” a couple of time: clp or tabling components operate in such islands while classical (impure) Prolog code provides the “glue”.

Yes! And of course, one can have purely functional islands in their C or C++ code just like one can have logical islands in their Prolog code. The real difficult part seems to be the judgements one has to make along the way. Which part of your application needs constraints? Which part is truly functional and which part is inherently stateful? What can be done with a regular expression and what is impossible?

Dogmatic thinking that takes away the burden of judgements is just so attractive… and then we end up with strong, comforting messages like this one:

This is because constraints are easy to explain, understand and use due to their purely relational nature. In contrast, the modedness and directionality of low-level arithmetic primitives are impure limitations that are better deferred to more advanced lectures.

Well

[emiruz]

I guess the trouble is that the right amount of dogma is not zero. It makes programming life and the adoption of new things much easier. And its certainly not zero if the dogma is true.

For practical things – such as programming for most people – conflation of a paradigm with its best known representative is a useful heuristic. I like Prolog because I can’t believe its even possible. Its a beautiful idea, but convincing other programmers on that basis generalises poorly.

[Boris]

@emiruz

And its certainly not zero if the dogma is true.

It is possible that we put different meanings in the word “dogma”, which is not surprising. Notably biologists have been confused irreversibly.

When I wrote “dogmatic” I meant:

Dogma, in its broadest sense, is any belief held unquestioningly and with undefended certainty.

Wikipedia

and yes, it is clear that the right amount of dogma is about zero, including the truth of this very statement.

[brebs]

@mizlan

I want the code to: tell me solutions

Firstly, write a predicate which works with clpfd variables:

include_gt([], _, []).
include_gt([H|T], I, [H|IL]) :-
    H #> I,
    include_gt(T, I, IL).
include_gt([H|T], I, IL) :-
    H #=< I,
    include_gt(T, I, IL).

Then it will work as intended:

?- include_gt([K], 3, L).
L = [K],
K in 4..sup ;
L = [],
K in inf..3.

[mizlan]

Yep, I ended up with something very similar to this! It is interesting to see the difference between having two clauses (which Prolog can backtrack by trying the other clause), and a ->/; construct, which is semantically completely different. (Correct me if that interpretation is misguided.)

I appreciate all the interesting discussion raised in these comments, which I initially wrote off as a bit off-topic but now can better grasp as it relates to how to think about programming in Prolog.

[peter.ludemann]

To answer my earlier question about replacing -> with *-> (“soft cut”), the answer is “no” (which is “obvious” when I thought about it a bit more).

You could use this modified version of include/3:

:- meta_predicate include(1, 1, +, -).
include(IncludeGoal, ExcludeGoal, List, ListIncluded) :-
    include_(List, IncludeGoal, ExcludeGoal, ListIncluded).

include_([], _, _, []).
include_([X|Xs], IncludeGoal, ExcludeGoal, [X|Included]) :-
    call(IncludeGoal, X),
    include_(Xs, IncludeGoal, ExcludeGoal, Included).
include_([X|Xs], IncludeGoal, ExcludeGoal, Included) :-
    call(ExcludeGoal, X),
    include_(Xs, IncludeGoal, ExcludeGoal, Included).

?- include(#>(3), #=<(3), [K], L).
L = [K],
K in inf..2 ;
L = [],
K in 3..sup.

[brebs]

@peter.ludemann

L = [K],
K in inf..2 ;

Should be K in 4..sup

[brebs]

@j4n_bur53

Evasion

Another strategy is to delay (do as late as possible) such a filtered list (which forces a #> choice)

[ridgeworks]

@j4n_bur53

… and choice points are not created:

Exactly. Put another way, defining constraints is always semi-deterministic (fails or succeeds exactly once). Generation of solutions (e.g., labelling in CLPFD) may be, and often is, non-deterministic.

Interesting example because it exposes the “rewriting” process that many CLP’s do, i.e., the breaking down of complex constraint expressions to simpler primitive constraints:

@j4n_bur53

?- X #= 42 #\/ X #= Y #\/ X #= 1001, X #> 500, X #> 400.
_A in 0..1,
X#=Y#<==>_A,
_A#\/_B#<==>1,
X in 501..sup,
X#=1001#<==>_B,
_B in 0..1.

[kuniaki.mukai]

@j4n_bur53

But isn’t it implementable somehow in CLP(FD)? If I remember well
@kuniaki.mukai ZDD can do such things? Or can’t it?

No. It can’t. It (mine) only translates a proposition to
its logically equivalent DNF whose conjunction has not a complementary-pair, and in addition counts the number of solutions (assignments) if required. However ZDD for finite domain constraint calculus sounds somehow possible, though specification of the goal of the problem is unclear for me, who is not familiar with it.

[ridgeworks]

@brebs

@emiruz

should use CLPFD for all arithmetic, all the time

I disagree - use it when there’s a good reason - it:

• Adds complexity (attributed variables)
• Is highly problem-dependent on whether performance increases, or (more likely) decreases
• Makes debugging harder

Probably all true, but I think they only apply when an arithmetic expression contains variables at evaluation time. Of course, standard Prolog arithmetic just produces an error when this occurs. So the underlying question is what are the desired semantics when variables occur in arithmetic expressions - error or constraint.

My hypothesis: If you have a purely integer problem that worked with standard arithmetic, you could replace any arithmetic expressions with their clpfd equivalent and see very little difference.

[brebs]

@ridgeworks

and see very little difference

If a beginner writes:

?- (X > 5 -> writeln('>5') ; writeln('not >5')).
ERROR: Arguments are not sufficiently instantiated

The above instantly shows the mistake (X must be ground). Whereas:

?- (X #> 5 -> writeln('>5') ; writeln('not >5')).
>5
X in 6..sup.

… hides the mistake and probably causes some frustration.

[ridgeworks]

As I said:

@ridgeworks

So the underlying question is what are the desired semantics when variables occur in arithmetic expressions - error or constraint.

For your example, you assume error semantics so it’s a “mistake”, but I suggest the second answer is equally valid. Logically speaking, you asserted the the variable X is an integer greater than 5, write a message to the console verifying that was so, and succeeded with the answer "X is an integer in range 6..sup. But because we’re all conditioned to expect an error, this is considered a mistake.

For the record, I’m not advocating replacing functional, ground arithmetic with anything else (that ship sailed a long time ago); just that it’s not not as wrong headed as might first appear. But CLP’s are readily (and optionally) available as libraries so I’m in agreement that you should …

@brebs

use it when there’s a good reason

[j4n_bur53]

Scryer Prolog CLP(Z) ships, not yet available in SWI-Prolog CLP(FD):

clpz_t(X, T) :-
        X #<==> #B,
        zo_t(B, T).

zo_t(0, false).
zo_t(1, true).

#=(X, Y, T) :- clpz_t(X #= Y, T).

#<(X, Y, T) :- clpz_t(X #< Y, T).

Feature: general CLP(Z) reification predicate
https://github.com/mthom/scryer-prolog/issues/2225#issuecomment-1890801923

Some explanation:

Appreciating clpz_t/2
https://github.com/mthom/scryer-prolog/discussions/2320