Binary - Decimal - Prologue
I found this on the stack: reversible "binary number" predicate
But I do not 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 requests:
?- binary_number([1,0,1], N). N = 5. ?- binary_number(Bs, 5). Bs = [1, 0, 1] .
Can someone explain the code to me
Specifically: binary_number([], _, N, N).
(_ _)
And what does the library (clpfd) do?
Why reverse(Bs0, Bs)
? I took it back, it still works great ...
thanks in advance
source to share
In the original, binary_number([], _, N, N).
value _
means that you don't care what the value of the variable is. If you used binary_number([], X, N, N).
(not caring what X
) Prolog will issue a single variable warning. In addition to what this sentence of predicates says, when the first argument is []
an empty list, then the third and fourth arguments are unified.
As explained in the comments, use_module(library(clpfd))
forces Prolog to use a library for programming Constraint logic across finite domains. You can also find a lot of useful information about this through a Google search for "clpfd prologue".
Typically in Prolog, comparison arithmetic expressions require the expressions to be fully constructed:
X + Y =:= Z + 2. % Requires X, Y, and Z to be instantiated
Prolog would evaluate and perform the comparison and give true or false. It would throw an error if any of these variables were not created. Likewise, for assignment, the predicate is/2
requires the right side expression to be fully parsed with specific variables, all created:
Z is X + Y. % Requires X and Y to be instantiated
Using CLPFD, you can have Prolog "examine" solutions for you. And you can also specify in which scope you want to restrict the variables. So you can say X + Y #= Z + 2
and Prolog can list possible solutions in X
, Y
and Z
.
As an aside, the original implementation could be refactored slightly to avoid exponentiation every time and eliminate 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 like:
| ?- 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 ending issues as pointed out in the comments, for cases like Bs = [1|_], N #=< 5, binary_number(Bs, N).
A the solution was provided by @false which just modifies the above helps to resolve these completion issues. I'll repeat this solution 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).
source to share