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 [tag:clpfd]. There are simpler examples. `factorial/2` is good start. — false, Jan 05 '15 at 22:18
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, Jan 05 '15 at 22:40
Why do you look at more complex queries? Look at simpler ones. — false, Jan 05 '15 at 22:43
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, Jan 05 '15 at 22:47
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, Jan 05 '15 at 22:56
No what I said was that I understand factorial in prolog. Never said I did with the clpfd.... But now I do thx by the way — Igor Beaufils, Jan 06 '15 at 06:31

score 1 · Accepted Answer · edited May 23 '17 at 12:07

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

Thx a lot for your precision, and your time. You should be a teacher :) — Igor Beaufils, Jan 06 '15 at 21:46
Lots of termination problems. See [this](http://stackoverflow.com/a/28442760/772868) — false, Feb 13 '15 at 20:40
@false thanks, I will indeed study that. My edit here was to take a clunky solution I posted before, which also had similar termination issues, and make it less clunky. But you're right: the termination issues remain. — lurker, Feb 13 '15 at 21:05

Binary to decimal - prolog

1 Answers1

Linked