I'm learning prolog using SWI Prolog and the tutorial here. I find that if I express the collatz conjecture exactly like they do in the video, it works as long as I replace #= with is which I'm guessing is a swipl vs scryer-prolog difference. But if I tweak the definition at all it seems to break, either with an error or incorrect conclusions. Why do my alternative definitions fail? Code:
use_module(library(clpfd)).
%% Does work, collatz_next(A, 1) gives A=2
collatz_next(N0, N) :-
N0 is 2*N.
collatz_next(N0, N) :-
N0 is 2*_ + 1,
N is 3*N0 + 1.
%% Doesn't work, collatz_next(A, 1) gives false
%% collatz_next(N0, N) :- ((N0 mod 2) is 0),((N0 / 2) is N).
%% collatz_next(N0, N) :- ((N0 mod 2) is 1),((N0 * 3 + 1) is N).
%% Doesn't work, collatz_next(A, 1) gives false
%% collatz_next(N0, N) :- ((N0 mod 2) is 0),(N0 is 2*N).
%% collatz_next(N0, N) :- ((N0 mod 2) is 1),((N0 * 3 + 1) is N).
%% Doesn't work
%% "Arguments are not sufficiently instantiated"
%% collatz_next(N0, N) :-
%% N0 / 2 is N.
%% collatz_next(N0, N) :-
%% N0 is 2*_ + 1,
%% N is 3*N0 + 1.
As brebs already wrote in the comments, you have to include the line :- use_module(library(clpfd)). if you are using SWI-Prolog. However, if you are using Scryer Prolog the library is called clpz, so you have to include the line :- use_module(library(clpz)).. The predicate collatz_next/2 (from the linked video) works with both Prologs as described in the video if you use the respective libraries (I tested it with Scryer Prolog version 0.9.0. and SWI-Prolog version 8.4.2, both 64bit on a linux machine). Since it has not been mentioned in the comments yet, I would also refer you to the description of CLP(FD) and CLP(Z) in The Power of Prolog.
Now to your question about the failing alternatives. The built-in is/2 is true if the expression on the right hand side evaluates to the number on the left hand side. If the left hand side is an uninstantiated variable, the variable contains the value of the expression on the right hand side after the call of the goal. In order for this to succeed all variables in the expression on the right hand side need to be instatiated. Consider the following examples:
?- 3 is 2+1. true. ?- X is 2+1. X = 3. ?- 3 is X+1. ERROR: Arguments are not sufficiently instantiated ... ?- 3 is 2+X. ERROR: Arguments are not sufficiently instantiated ...
Furthermore if the left hand side is instantiated with a float rather than with an integer is/2 will fail:
?- 3.0 is 2+1. false.
Now that we covered some basics let's take a look at your first predicate:
%% Does work, collatz_next(A, 1) gives A=2 collatz_next(N0, N) :- N0 is 2*N. collatz_next(N0, N) :- N0 is 2*_ + 1, N is 3*N0 + 1.
Let's observe that, while your given example produces a correct answer, after pressing the ;-key it throws an instantiation error:
?- collatz_next(A, 1). A = 2 ; ERROR: Arguments are not sufficiently instantiated ...
What's going on here? You're posting the query collatz_next(A, 1)., hence the variable N0 in the head of your predicate is unified with the variable A and the variable N is unified with 1. With these unifications the only goal in the first rule, N0 is 2*N, now becomes A is 2*1. That yields the answer A = 2. Prolog now tries the second rule of collatz_next/2, where the first goal, N0 is 2*_ + 1 now becomes A is 2*_ + 1. Here the right hand side still contains a variable (_), hence the expression is not sufficiently instatiated to be evaluated thus Prolog throws an instantiation error.
Now let's try to use the predicate the other way around. As you can see in the Youtube-video, if N0=5 then the expected answer is N=16. However, if you query that with your predicate you get no answer and an instantiation error:
?- collatz_next(5, N). ERROR: Arguments are not sufficiently instantiated ...
Looking at your definition of collatz_next/2 we can observe that the variable N0 in the head of the rule is unified with 5, while the second argument N remains uninstantiated. The single goal in the first rule, N0 is 2*N, becomes 5 is 2*N hence the instantiation error due to the variable on the right hand side.
Note, that the video is also showing that the most general query :- collatz_next(N0,N). is still producing answers due to the use of CLP(FD)/CLP(Z), while your version, using is/2, is again producing an instantiation error.
The next two versions of collatz_next/2 you posted (the ones with the comment %% Doesn't work, collatz_next(A, 1) gives false) fail with the first goal in the rules. Since you query :- collatz_next(A, 1). the variable N0 in the head of the rules is unified with the variable A, so the first goal in all four rules becomes ((A mod 2) is 0) and ((A mod 2) is 1) respectively. If you try these goals as queries the answer is false:
?- ((A mod 2) is 0). false. ?- ((A mod 2) is 1). false.
And since the first goal of the rule fails, Prolog won't even try the second goal because once you have a false in a (chain of) conjunction(s) it cannot yield true. This is the case for both rules of both predicates hence the answer to your queries is false. If you, on the other hand, try to exchange the left hand sides of is/2 with the right hand sides you will get an instantiation error:
?- (0 is (A mod 2)). ERROR: Arguments are not sufficiently instantiated ... ?- (1 is (A mod 2)). ERROR: Arguments are not sufficiently instantiated ...
Maybe think about it this way: What can you expect to happen if you try to evaluate an uninstantiated variable modulo an actual number? One reasonable expectation would be to get some sort of feedback stating that it can't be done.
Another reasonable point of view would be to expect Prolog to propagate the posted goal as a constraint until it can (hopefully) be solved at a later time. This is basically what CLP(FD)/CLP(Z) does (see also the section on Constraint propagation in CLP(FD) and CLP(Z) in The Power of Prolog. Just try the above queries with (#=)/2:
?- ((A mod 2) #= 0). A mod 2#=0. % residual goal ?- ((A mod 2) #= 1). A mod 2#=1. % residual goal ?- (0 #= (A mod 2)). A mod 2#=0. % residual goal ?- (1 #= (A mod 2)). A mod 2#=1. % residual goal
As you can see, the posted constraints are now propagated and appear as residual goals at the end of the deduction since in these cases, with the queries just consisting of those single goals, they cannot be further resolved.
The last version you posted (marked with the comment %% Doesn't work) has the left hand side and the right hand side of is/2 the wrong way around in the single goal of the first rule, as pointed out by TessellatingHeckler in the comments. But even if you exchange them you will get an instantiation error unless the variable N0 is instantiated. But even then you will still get an instantiation error once Prolog tries the second rule because its first goal N0 is 2*_ + 1 contains a variable _ that is always uninstantiated:
?- N0 is 2*_ + 1. ERROR: Arguments are not sufficiently instantiated ... ?- 1 is 2*_ + 1. ERROR: Arguments are not sufficiently instantiated ...
The bottom line is: If you want to use low-level predicates like is/2 you have to be aware of their limitations. If you want to declaratively reason over integers you can't easily get around CLP(FD)/CLP(Z). And if you decide to use a predicate like collatz_next/2 as presented in the video, you can't exchange CLP(FD)/CLP(Z)-constraints one-to-one for low-level predicates like is/2 and expect the same results.