2

I'm trying to convert a list of bytes to it's corresponding integer. I would like to bind to the second variable as the documenting comment would suggest. I'm printing it out as a temporary hack.

% bytes_int(+ByteList, -IntegerRepresentation)
%  converts a list of bytes to integer representation
%  I accounts for bitshifting
bytes_int(BytesList, _) :-
    bytes_int(BytesList, 0, 0).

bytes_int([], _, Num) :-
    format('~w', Num).
bytes_int([B|Bs], I, Num) :-
    B0 is B << I,
    Num0 is B0 + Num,
    I0 is I + 8,
    bytes_int(Bs, I0, Num0).

It's printing the correct value, but I'm not sure why it's not binding to the second variable for further use. What improvements can I do to accomplish this?

?- bytes_int([42, 121, 56], N).
3701034
4

2 回答 2

4

I would like to expand a bit on the nice answer by @WillemVanOnsem. Here is the version he posted:

bytes_int(BytesList, R) :-
    bytes_int(BytesList, 0, 0, R).

bytes_int([], _, R, R).
bytes_int([H|T], S0, R0, R) :-
    R1 is R0 + H << S0,
    S1 is S0 + 8,
    bytes_int(T, S1, R1, R).

So, let us try a few queries. First, the test case provided in the question:

?- bytes_int([42,121,56], I).
I = 3701034.

Nice, it works. So let us try a more general case, where I query about three bytes, but do not specify their values:

?- bytes_int([A,B,C], I).
ERROR: Arguments are not sufficiently instantiated

Unfortunately, this does not work: The use of low-level integer arithmetic precludes such more general use cases. This limitation carries over to all yet more general queries, even though they may sometimes yield a solution:

?- bytes_int(Bs, I).
Bs = [],
I = 0 ;
ERROR: Arguments are not sufficiently instantiated

What about the more specific case where at least the second argument is fully instantiated:

?- bytes_int(Bs, 3701034).
ERROR: Arguments are not sufficiently instantiated

No, the predicate is not capable to yield any answer in this case either.

Well, that's all to be expected, more imperatively inclined programmers will say at this point. What do you think we are? Declarative programmers?

Yes.

So, I make the following straight-forward change to the version above in order to make it more declarative: I replace (is)/2 with (#=)/2. Yes I know, the books from 40 years ago do not do this, but still let's do it and see what we get in return:

bytes_int(BytesList, R) :-
    bytes_int(BytesList, 0, 0, R).

bytes_int([], _, R, R).
bytes_int([H|T], S0, R0, R) :-
    R1 #= R0 + H << S0,
    S1 #= S0 + 8,
    bytes_int(T, S1, R1, R).

Let's start right away with the most general query, where we simply ask for any answer whatsoever:

?- bytes_int(Bs, I).
Bs = [],
I = 0 ;
Bs = [_15310],
I#=_15310<<0 ;
Bs = [_16050, _16056],
_16086#=_16050<<0,
_16086+_16118#=I,
_16118#=_16056<<8 .

Nice! So we now get more answers. In fact, we can now test nontermination:

?- bytes_int(Bs, I), false.
nontermination

The fact that this query doesn't terminate is reassuring: Since the predicate ought to hold for lists of arbitrary length, it must not terminate universally.

Let's try a few more cases:

?- bytes_int([A,B,C], I).
_3674#=A<<0,
_3674+_3706#=_3700,
_3706#=B<<8,
_3700+_3754#=I,
_3754#=C<<16.

This is the case from above: We now get a symbolic representation of all answers, which is sometimes quite useful.

In particular, the original test case of course follows naturally as a special case of that more general query:

?- bytes_int([42,121,56], I).
I = 3701034.

This works exactly as before.

So there is one case left to test: What about the second argument being instantiated?

?- bytes_int(Bs, 3701034).
Bs = [_5164],
3701034#=_5164<<0 ;
Bs = [_6056, _6062],
_6080#=_6056<<0,
_6080+_6112#=3701034,
_6112#=_6062<<8 .

This at least yields answers. I leave it as an exercise to improve upon this. Recall that so far, all I did was simply to replace (is)/2 by (#=)/2, and this alone has already significantly increased the generality of this relation. Depending on your Prolog system, you may currently need to import a library to benefit from this declarative integer arithmetic.

于 2017-03-17T18:08:25.207 回答
3

A first problem that occurs is here:

bytes_int(BytesList, _) :-
    bytes_int(BytesList, 0, 0).

You do not bind the result (_) with a variable in the call. You probably want to use:

bytes_int(BytesList, R) :-
    bytes_int(BytesList, 0, R).

Next you do not use an accumulator. The accumulator here can store the cumulative sum you have obtained this far. So we declare an additional parameter:

bytes_int(BytesList, R) :-
    bytes_int(BytesList, 0, 0, R).

Now we are set for the real algorithm. In case we reached the end of the list. The thus far cumulative sum, is the final result so:

bytes_int([], _, R, R).

In the other case, we simply update the cumulative sum, update the shift size, and perform recursion on the tail of the list:

bytes_int([H|T], S0, R0, R) :-
    R1 is R0 + H << S0,
    S1 is S0 + 8,
    bytes_int(T, S1, R1, R).

And now putting it all together:

bytes_int(BytesList, R) :-
    bytes_int(BytesList, 0, 0, R).

bytes_int([], _, R, R).
bytes_int([H|T], S0, R0, R) :-
    R1 is R0 + H << S0,
    S1 is S0 + 8,
    bytes_int(T, S1, R1, R).

This generates:

?- bytes_int([42, 121, 56], N).
N = 3701034.
于 2017-03-17T16:13:08.727 回答