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

Question

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

让我用一些代码来说明.假设我有一个二进制协议.我想从一个字节读取两个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)或自己实现整个约束机制。通过一些巧妙的限制，您可能会采用更简单的方法，但我怀疑这是否会奏效。权衡是在正确性和效率方面。请注意，clpfdSICStus 或 SWI 的系统实际上需要几十年才能达到其质量水平。

无论您选择哪种方式，请注意以下几点：

效率library(clpfd)

library(clpfd)SWI-Prolog 中的内容经过专门优化，在性能上（在某些情况下）可与传统的(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 不支持。所以一些额外的头痛在这里等着你。但只要您使用无符号非负值，就不会出现问题。对于一般轮班，您需要(^)/2SWI 支持，但 SICStus 不支持。

这是 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)可能会进一步得到显着改进，但为了改进它们，必须使用它们！

输入/输出和pio

ISO Prolog 支持基本 I/O 操作

• 字节 ( get_byte/1),
• 代码 ( get_code/1) 和
• 人物 （get_char/1）。

如果您想使用 DCG，您肯定会想使用library(pio). 目前，SWIlibrary(pio)仅支持codes.