在 Prolog 中将字节列表转换为整数

Question

我正在尝试将字节列表转换为相应的整数。我想按照文档注释的建议绑定到第二个变量。我将其作为临时 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).

它正在打印正确的值，但我不确定为什么它没有绑定到第二个变量以供进一步使用。我可以做哪些改进来实现这一目标？

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

Answer 1

出现的第一个问题是：

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

您不要在调用中将结果 (_) 与变量 绑定。您可能想使用：

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

接下来你不使用累加器。这里的累加器可以存储你目前获得的累计和。所以我们声明一个额外的参数：

bytes_int(BytesList, R) :-
    bytes_int(BytesList, 0<b>, 0</b>, R).

现在我们已经为真正的算法做好了准备。以防我们到达列表的末尾。到目前为止的累计总和，就是最终的结果：

bytes_int([], _, <b>R, R</b>).

在另一种情况下，我们简单地更新累积和，更新移位大小，并对列表的尾部执行递归：

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

现在把它们放在一起：

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

这会生成：

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

Answer 2

我想扩展一下@WillemVanOnsem 的精彩回答。这是他发布的版本：

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

那么，让我们尝试一些查询。一、题目中提供的测试用例：

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

很好，很管用。那么让我们尝试一个更一般的情况，我查询 三个字节 ，但不指定它们的值：

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

不幸的是，这不起作用：低级整数运算的使用排除了这种更一般的用例。此限制适用于所有更一般的查询，即使它们有时可能会产生解决方案：

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

至少 second 参数被完全实例化的更具体的情况呢：

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

不，谓词在这种情况下也不能产生任何答案。

好吧，这都是意料之中的，更多命令式倾向的程序员会在这一点上说。你以为我们是什么？ 声明式程序员？

是的。

因此，我对上面的版本进行了以下直接更改，以使其更具声明性：我将 (is)/2 替换为 (#=)/2。是的，我知道，40 年前的书不会这样做，但我们仍然这样做，看看我们在 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).

让我们立即开始最一般的查询，在这里我们只需要任何答案:

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

不错！所以我们现在得到了更多的答案。事实上，我们现在可以 test nontermination:

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

这个查询不会终止的事实令人安心：由于谓词应该适用于任意长度的列表，它一定不会 普遍终止。

我们再试几个案例：

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

这是上面的情况：我们现在得到所有答案的符号表示，这有时非常有用。

特别是，原始测试用例当然会自然地成为该更一般查询的特例：

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

这与以前完全一样。

所以还有一种情况需要测试：second 参数被实例化怎么样？

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

这至少会产生答案。我把它留作改进这一点的练习。回想一下，到目前为止，我所做的只是简单地将 (is)/2 替换为 (#=)/2，仅此一项就已经显着增加了这种关系的普遍性。根据您的 Prolog 系统，您当前可能需要导入一个库才能从这个 声明式 整数算法中受益。

在 Prolog 中将字节列表转换为整数

Converting a list of Bytes to Integer in Prolog

prolog

byte-shifting

是的。