reversible "binary to number" predicate

Question

What is the best way to convert binary bits (it might be a list of 0/1, for example) into numbers in a reversible way. I've written a native predicate in swi, but is there better solution ? Best regards

Option

What should be the answer for the following query: binary_number(B, -5).: an exception like Domain error: `not_less_than_zero' expected, found `-5' or failure (no / false)? – Carouse

@TudorBerariu: As you like. Both failure and some error is fine. (BTW; I did not read your question before, you need to @ me) – Shellieshellproof

Answer 1

Use CLP(FD) constraints, for example:

:- use_module(library(clpfd)).

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

binary_number_(B, I0-N0, I-N) :-
        B in 0..1,
        N #= N0 + B*2^I0,
        I #= I0 + 1.

Example queries:

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

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

?- binary_number(Bs, N).
Bs = [],
N = 0 ;
Bs = [N],
N in 0..1 ;
etc.

Residence

binary_number(Bs, 5). does not terminate. – Shellieshellproof

That is to be expected: In this representation, using a list of 0 and 1 for binary numbers, an arbitrary number of "0" can be prepended to the list while still denoting the same integer. – Residence

OP asked for a reversible predicate. In any case, binary_number([1|_],1) has no leading zeros whatsoever. – Shellieshellproof

It is the requirement for reversibility that makes this behaviour necessary. Suppose Bs = [1,0,1] were the only solution for binary_number(Bs, 5). Thus, Bs = [0,0,0,1,0,1], binary_number(Bs, 5) would succeed, but exchanging the goals by commutativity of conjunction would fail, making the predicate not reversible. – Residence

See this answer for a solution that is - as much as (probably) possible - reversible. – Shellieshellproof

Answer 2

Here is the solution I was thinking of, or rather what I hoped exists.

:- use_module(library(clpfd)).

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

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

This solution also terminates for queries like:

?- Bs = [1|_], N #=< 5, binary_number(Bs, N).

Shellieshellproof

This is an elegant, simple way around the termination issue (+1) and avoids the exponentiation (:)). – Hankering

I don't understand the purpose of M. Can't you remove it and replace it in M #>= N1 by N? – Cancel

@Fatalize: M, thus the 4th argument is needed to ensure that the predicate is really reversible. It is the original variable... – Shellieshellproof

Answer 3

The solution

This answer seeks to provide a predicate binary_number/2 that presents both logical-purity and the best termination properties. I've used when/2 in order to stop queries like canonical_binary_number(B, 10) from going into infinite looping after finding the first (unique) solution. There is a trade-off, of course, the program has redundant goals now.

canonical_binary_number([0], 0).
canonical_binary_number([1], 1).
canonical_binary_number([1|Bits], Number):-
    when(ground(Number),
         (Number > 1,
          Pow is floor(log(Number) / log(2)),
          Number1 is Number - 2 ^ Pow,
          (   Number1 > 1
           -> Pow1 is floor(log(Number1) / log(2)) + 1
           ;  Pow1 = 1
         ))),
    length(Bits, Pow),
    between(1, Pow, Pow1),
    length(Bits1, Pow1),
    append(Zeros, Bits1, Bits),
    maplist(=(0), Zeros),
    canonical_binary_number(Bits1, Number1),
    Number is Number1 + 2 ^ Pow.

binary_number(Bits, Number):-
    canonical_binary_number(Bits, Number).
binary_number([0|Bits], Number):-
    binary_number(Bits, Number).

Purity and termination

I claim that this predicate presents logical-purity from construction. I hope I got it right from these answers: one, two and three.

Any goal with proper arguments terminates. If arguments need to be checked, the simplest way to achieve this is using the built-in length/2:

binary_number(Bits, Number):-
    length(_, Number),
    canonical_binary_number(Bits, Number).

?- binary_number(Bits, 2+3).
ERROR: length/2: Type error: `integer' expected, found `2+3'
   Exception: (6) binary_number(_G1642009, 2+3) ? abort
% Execution Aborted
?- binary_number(Bits, -1).
ERROR: length/2: Domain error: `not_less_than_zero' expected, found `-1'
   Exception: (6) binary_number(_G1642996, -1) ? creep

Example queries

?- binary_number([1,0,1|Tail], N).
Tail = [],
N = 5 ;
Tail = [0],
N = 10 ;
Tail = [1],
N = 11 ;
Tail = [0, 0],
N = 20 .

?- binary_number(Bits, 20).
Bits = [1, 0, 1, 0, 0] ;
Bits = [0, 1, 0, 1, 0, 0] ;
Bits = [0, 0, 1, 0, 1, 0, 0] ;
Bits = [0, 0, 0, 1, 0, 1, 0, 0] ;
Bits = [0, 0, 0, 0, 1, 0, 1, 0, 0] .

?- binary_number(Bits, N).
Bits = [0],
N = 0 ;
Bits = [1],
N = 1 ;
Bits = [1, 0],
N = 2 ;
Bits = [1, 1],
N = 3 ;
Bits = [1, 0, 0],
N = 4 ;
Bits = [1, 0, 1],
N = 5 .

Carouse

binary_number(L,-1) loops – Shellieshellproof

It's outside the domain of the second argument. I can add some conditions like length(_, Number) and exceptions will be thrown. – Carouse

Answer 4

playing with bits...

binary_number(Bs, N) :-
    var(N) -> foldl(shift, Bs, 0, N) ; bitgen(N, Rs), reverse(Rs, Bs).

shift(B, C, R) :-
    R is (C << 1) + B.

bitgen(N, [B|Bs]) :-
    B is N /\ 1 , ( N > 1 -> M is N >> 1, bitgen(M, Bs) ; Bs = [] ).

Abstracted

Answer 5

Can use recursion, instead of reverse/2:

binary_list_int([1|T], I) :-
    (   integer(I)
    ->  I @>= 1
    ;   var(I)
    ),
    binary_list_int_(T, 1, _, 1, I, I).

binary_list_int_([], H, 1, _M, _N, I) :-
    binary_list_int_digit_(H, 1, I).
binary_list_int_([H|T], P, U1, M, N, I) :-
    M1 is M * 2,
    % Prevent increasing into infinity
    (   nonvar(N)
    ->  N @>= M1
    ;   true
    ),
    binary_list_int_(T, H, U, M1, N, I0),
    U1 is U * 2,
    binary_list_int_digit_(P, U1, B),
    I is I0 + B.

binary_list_int_digit_(0, _, 0).
binary_list_int_digit_(1, U, U).

Results in swi-prolog:

% Terminates
?- binary_list_int(Bs, 5).
Bs = [1, 0, 1] ;
false.

% Prevents leading zero
?- between(0, 5, I), binary_list_int(Bs, I).
I = 1,
Bs = [1] ;
I = 2,
Bs = [1, 0] ;
I = 3,
Bs = [1, 1] ;
I = 4,
Bs = [1, 0, 0] ;
I = 5,
Bs = [1, 0, 1] ;
false.

% No unwanted choicepoint, when providing list
?- binary_list_int([1,1,0,0,0], I).
I = 24.

?- binary_list_int(Bs, I).
Bs = [1],
I = 1 ;
Bs = [1, 0],
I = 2 ;
Bs = [1, 1],
I = 3 ;
Bs = [1, 0, 0],
I = 4 ;
Bs = [1, 1, 0],
I = 6 ;
Bs = [1, 0, 1],
I = 5 ;
Bs = [1, 1, 1],
I = 7 ;
Bs = [1, 0, 0, 0],
I = 8 ;

% Prevents invalid input
?- binary_list_int(Bs, -5).
false.

Goiter