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

Question

在我看来，使用DCGs处理字节列表中的二进制数据应该是可行的。然而为了使其通用，必须使用位运算符，这意味着需要使用 is/2，这也意味着实例化顺序是一个问题，这可能会使DCGs在解析和生成时变得混乱。这里的想法是序列化/反序列化二进制数据，但我认为这个示例足够简单，可以说明问题。

让我用一些代码来说明。假设我有一个二进制协议。我想从一个字节中读取两个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的位语法之类的东西，但搜索没有任何运气。

- Daniel Lyons

---

一方面你准确地抱怨了(is)/2是被调整模式的，但另一方面你又“担心在低级代码中调用如此强大的系统[如clpfd]会产生性能影响”。你必须做出选择。移位与乘法、除法和指数相关... - false

“is/2” 在右侧未绑定的术语上无法工作。想象一下，如果它可以工作，Prolog 将不得不为所有算术运算定义（更加可疑的）反函数。特别是对于像“>>/2”这样的运算符，这似乎很奇怪（“A >> B”应该生成什么？以及以什么顺序？）。 - Patrick J. S.

@PatrickJ.S. 我非常清楚 is/2 的局限性。我并不是说我需要 is/2。我是想要解析和生成，而且我怀疑在实践中 clpfd 会太重了。如果有证据证明我错了，我很乐意接受。 - Daniel Lyons

@lurker：虽然你的方法可能有效，但它会为“非关系型”错误打开一个广阔的领域。相比之下，使用clpfd则完全不会发生这样的错误。 - false

我在库代码中看到了一些情况，其中读取和生成DCG是分开的，就像你所遇到的情况一样。换句话说，你有一个DCG，它首先进行映射然后转换（解析），另一个则首先转换然后映射（写入）。 - user1812457

Answer 1

更好地支持二进制数据是Prolog中一个非常好的功能。然而，Prolog的关系性质使得一般解决方案相当困难。因此，你面临着一个严重的决定：要么将其他语言的某些库直接映射到Prolog中，从而忽略Prolog的关系性质（并理想情况下避免所有边界与干净实例化错误），要么选择更具关系性的方法。

在选择更具关系性的解决方案时，你可以使用现有的库，如library(clfd)，或者自己实现整个约束机制。通过一些巧妙的限制，你可以采用更简单的方法，但我怀疑这种方法是否可行。权衡的领域在于正确性和效率。请注意，SICStus或SWI中的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不支持。因此，在这里会有一些额外的麻烦。但只要您使用无符号非负值，就不会出现问题。对于一般的位移，您将需要(^)/2，这是由SWI支持的，但不是由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 支持对字节 (get_byte/1)、代码 (get_code/1) 和字符 (get_char/1) 进行基本的输入/输出操作。

如果您想使用 DCGs，则一定要使用 library(pio)。目前，SWI 的 library(pio) 仅支持 codes。

- false

---

这个答案让我想立刻尝试一下CLP(FD)，谢谢！ - Wouter Beek

@Boris：SWI曾计划加入流和输出功能，但不幸的是，SWI采取了另一种方向。 - false

@WouterBeek：phrase_from_stream/2需要一个可寻址的设备。至于输出：甚至有一个版本可以透明地执行此操作。回溯并不会使事情变得太复杂。 - false

@WouterBeek 是的，例如它不能在标准输入上工作。phrase_from_stream - user1812457

@false: 说得好！更高级的库还能在哪里找到？ - Wouter Beek

Answer 2

在SWI-Prolog中，CLP(FD)现在支持许多位运算。请尝试使用最新的git版本，并将您的代码中的(is)/2替换为(#=)/2：

two_four_bit_ints(High, Low) -->
  [B],
  {
    High #= B >> 4,
    Low  #= B /\ 0xF
  }。

前4个示例查询与以前完全相同，并且应该具有可接受的效率：

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

请注意，如果CLP(FD)约束用于也支持原始算术的模式，则直接编译为低级谓词。

使用CLP(FD)约束的好处之一是其他2个查询现在也有效：

?- phrase(two_four_bit_ints(15,15), [X]).
15 #= X/\15,
15 #= X>>4.
?- phrase(two_four_bit_ints(15,15), X).
X = [_G1048],
15#=_G1048/\15,
15#=_G1048>>4.

至少您可以将其用于进一步的推理。

实际上，最普通的查询现在也有效：

?- phrase(two_four_bit_ints(A,B), X).
X = [_G1270],
A #= _G1270>>4,
B #= _G1270/\15.

在某些情况下可能可以执行更强大的传播。如果需要，我会尽快研究这个问题。

- mat

Answer 3

为了比评论更加明确，以解析整数和将整数转换回字符串为例，你可以这样说：

foo_parse(Number) -->
    digits(Ds),
    { number_codes(Number, Ds) }.

foo_generate(Number) -->
    { number_codes(Number, Ds) },
    Ds.

你可以通过在两个子句的第一个位置添加 var(Number) "保护"，并配合自己的 cut 等来避免这种情况，但我不确定它是否更容易编写、阅读或使用。两个 DCG 可能会从不同的上下文中调用。

因此，对于你的情况，生成的代码将类似于：

fourbit_fourbit_generate(High, Low) -->
    { D is (High << 4) + Low },
    [D].

只是我的观点。

- user1812457

Answer 4

这可以工作。

two_four_bit_ints(High, Low) -->
 [B],
  {
     integer(B) % suggestion by @false, instead of nonvar(B)
  -> High is B >> 4,
     Low  is B /\ 0xF
  ;  B is (High << 4) \/ Low
  }.

记住，DCG只是普通的Prolog，但你可以把它们看作可执行的语义语法。

- CapelliC