Prolog - 使用 DCG 处理二进制数据

Question

在我看来，应该能够使用字节列表上的 DCG 处理二进制数据。但是，要使其正常工作，必须使用按位运算，这意味着 is/2涉及，这意味着实例化顺序是一个问题，这可能会混淆使用 DCG 进行解析和生成。这里的想法是序列化/反序列化二进制数据，但我认为这个例子很简单，足以说明问题。

让我用一些代码来说明。假设我有一个二进制协议(protocol)。我想从一个字节中读取两个 4 位整数。我天真的自我尝试了这个:

two_four_bit_ints(High, Low) -->
  [B],
  {
    High is B >> 4,
    Low  is B /\ 0xF
  }.

这似乎适用于解析:

?- phrase(two_four_bit_ints(H,L), [255]).
H = L, L = 15.

?- phrase(two_four_bit_ints(H,L), [0]).
H = L, L = 0.

?- phrase(two_four_bit_ints(H,L), [15]).
H = 0,
L = 15.

?- phrase(two_four_bit_ints(H,L), [240]).
H = 15,
L = 0.

但这不会产生:

?- phrase(two_four_bit_ints(15,15), [X]).
ERROR: is/2: Arguments are not sufficiently instantiated

?- phrase(two_four_bit_ints(15,15), X).
ERROR: is/2: Arguments are not sufficiently instantiated

不知道该怎么办。我正准备让某人喊“使用 clpfd”，但它似乎不支持位移操作，而且我担心在低级代码中间调用如此强大的系统的性能影响。

由于我没有看到很多二进制助手，在 Prolog 中是否有其他更优选的二进制提取/编码方式？我现在只使用 SWI，所以我很乐意接受不能移植到 ISO 的建议，但如果它是可移植的，那也很好。我宁愿找到有人移植了 Erlang 的位语法之类的东西，但没有找到任何运气。

Answer 1

更好地支持二进制数据将是 Prolog 中的一个非常好的功能。然而，Prolog 的关系特性使得通用解决方案非常困难。所以你面临一个严肃的决定:要么将一些其他语言的库直接映射到 Prolog，从而忽略 Prolog 的关系性质(理想情况下避免所有边界与干净的实例化错误)，要么选择更关系的方法。

选择更加关系的解决方案时，您可以使用现有库为library(clfd)或自己实现整个约束机制。通过一些巧妙的限制，您可能会采用更简单的方法，但我怀疑这会奏效。权衡是在正确性和效率方面。请注意，SICStus 或 SWI 中的 clpfd 系统实际上需要数十年才能达到其质量水平。

无论您采取哪种方式，请注意:
library(clpfd)的效率

SWI-Prolog 中的 library(clpfd) 经过专门优化，在性能上(在某些情况下)与传统的 (is)/2 相当。要看到这一点，请编译规则:

list_len([_|Es], N0) :- N0 #> 0, N1 #= N0-1, list_len(Es, N1).

并使用 listing(list_len) 查看生成的代码:

list_len([_|C], A) :-
    (   integer(A)
    ->  A>=0+1
    ;   clpfd:clpfd_geq(A, 1)
    ),
    (   integer(A)
    ->  B is A+ -1
    ;   clpfd:clpfd_equal(B, A-1)
    ),
    list_len(C, B).

实际上，可评估表达式(如 (is)/2 和 (>=)/2)的内置函数用于直接对应于这些原始操作的情况。

但是，要完全模拟位移操作，您需要 (div)/2，目前仅 SICStus 的 library(clpfd) 支持但 SWI 不支持。所以一些额外的头痛会在这里等着你。但只要您使用无符号非负值，就不会出现问题。对于一般类次，您将需要 SWI 支持但 SICStus 不支持的 (^)/2。

这是 CLPFD 版本:

two_four_bit_ints(High, Low) -->
  [B],
  { B in 0..255,
    Low in 0..15,
    High in 0..15,
    B #= Low + High*16
  }.

请注意，您的原始程序无意中定义了相当意外情况下的行为，例如 B = -1234 、 B = 1+1 。您可以添加 between(0, 255, B) 但随后您将轻松获得组合枚举(阅读:爆炸)。

对于这种情况， library(clpfd) 的当前实现可能会进一步得到显着改进，但为了改进它们，必须使用它们!

I/O 和 pio
ISO Prolog 支持基本的 I/O 操作

字节(get_byte/1)，

代码 ( get_code/1 ) 和

个字符(get_char/1)。

如果你想使用 DCG，你肯定会想使用 library(pio) 。目前，
SWI 的 library(pio) 只支持 codes 。