Binary to decimal - prolog

Question

I found this on stack: reversible "binary to number" predicate

But I don't understand

:- use_module(library(clpfd)).

binary_number(Bs0, N) :-
        reverse(Bs0, Bs),
        binary_number(Bs, 0, 0, N).

binary_number([], _, N, N).
binary_number([B|Bs], I0, N0, N) :-
        B in 0..1,
        N1 #= N0 + (2^I0)*B,
        I1 #= I0 + 1,
        binary_number(Bs, I1, N1, N).

Example queries:

?- binary_number([1,0,1], N).
N = 5.

?- binary_number(Bs, 5).
Bs = [1, 0, 1] .

Could somebody explain me the code

Especialy this : binary_number([], _, N, N). (The _ )

Also what does library(clpfd) do ?

And why reverse(Bs0, Bs) ? I took it away it still works fine...

thx in advance

Try binary_number([1,0,0], N) to see that reverse/2 is needed. For library(clpfd) look at clpfd. There are simpler examples. factorial/2 is good start. — false
1 ?- binary_number([1,0,1,1,0,0,1], L). L = 77. I did that why I don't understand what's its use. — Igor Beaufils
Why do you look at more complex queries? Look at simpler ones. — false
I need to convert binary to decimal. And I found this so I try to understand. The easy stuffs with factorial I know how to do. Beside one way to get better is to try hard stuffs — Igor Beaufils
You did not understand the factorial/2 example in clpfd. After all, you are asking "what does library(clpfd) do?" You would not ask this, would you have studied and understood factorial/2 here on SO. — false

lurker lurker · Accepted Answer · 2015-01-06T16:52:53

In the original, binary_number([], _, N, N)., the _ means you don't care what the value of the variable is. If you used, binary_number([], X, N, N). (not caring what X is), Prolog would issue a singleton variable warning. Also, what this predicate clause says is that when the first argument is [] (the empty list), then the 3rd and 4th arguments are unified.

As explained in the comments, use_module(library(clpfd)) causes Prolog to use the library for Constraint Logic Programming over Finite Domains. You can also find lots of good info on it via Google search of "prolog clpfd".

Normally, in Prolog, arithmetic expressions of comparison require that the expressions be fully instantiated:

X + Y =:= Z + 2.  % Requires X, Y, and Z to be instantiated

Prolog would evaluate and do the comparison and yield true or false. It would throw an error if any of these variables were not instantiated. Likewise, for assignment, the is/2 predicate requires that the right hand side expression be fully evaluable with specific variables all instantiated:

Z is X + Y.  % Requires X and Y to be instantiated

Using CLPFD you can have Prolog "explore" solutions for you. And you can further specify what domain you'd like to restrict the variables to. So, you can say X + Y #= Z + 2 and Prolog can enumerate possible solutions in X, Y, and Z.

As an aside, the original implementation could be refactored a little to avoid the exponentiation each time and to eliminate the reverse:

:- use_module(library(clpfd)).

binary_number(Bin, N) :-
    binary_number(Bin, 0, N).

binary_number([], N, N).
binary_number([Bit|Bits], Acc, N) :-
    Bit in 0..1,
    Acc1 #= Acc*2 + Bit,
    binary_number(Bits, Acc1, N).

This works well for queries such as:

| ?- binary_number([1,0,1,0], N).

N = 10 ? ;

no
| ?- binary_number(B, 10).

B = [1,0,1,0] ? ;
B = [0,1,0,1,0] ? ;
B = [0,0,1,0,1,0] ? ;
...

But it has termination issues, as pointed out in the comments, for cases such as, Bs = [1|_], N #=< 5, binary_number(Bs, N). A solution was presented by @false which simply modifies the above helps solve those termination issues. I'll reiterate that solution here for convenience:

:- use_module(library(clpfd)).

binary_number(Bits, N) :-
    binary_number_min(Bits, 0,N, N).

binary_number_min([], N,N, _M).
binary_number_min([Bit|Bits], N0,N, M) :-
    Bit in 0..1,
    N1 #= N0*2 + Bit,
    M #>= N1,
    binary_number_min(Bits, N1,N, M).

Binary to decimal - prolog

1 Answers