SWI-Prolog 使用移位 CLPFD 报告错误答案
SWI-Prolog reporting wrong answer with bitshifts CLPFD
我在一个更大的代码库中遇到过这个问题，但将其缩减为一个最小的可重现示例。这是汇编程序的一些代码：
:- use_module(library(clpfd)).
bigconst(X) :- X #=< 0x3FF, X #>= 0.
asm(instruction('ADD', [A]), R) :-
bigconst(A),
R #= 0b0000 + (A << 4).
asm(instruction('SUB', [A]), R) :-
bigconst(A),
R #= 0b0001 + (A << 4).
组装的时候好像可以用：
?- asm(instruction('SUB', [5]), R).
R = 81.
但是反汇编的时候好像失败了:
?- asm(I, 81).
I = instruction('ADD', [_42146]),
_42146 in 0..1023,
81#=_42146<<4 .
这是我程序中的错误还是 Prolog 中的错误？我该如何解决这个问题？
当我找到答案时，大声笑。我用过很多奇怪的模式来解决问题，但这是我以前从未使用过的。一旦我看到它的工作，我就知道我有一个用于工具箱的闪亮新工具。
对于 CLP(FD) 问题，它们通常可以双向工作，这正是您想要的。您遇到的第一个问题是您有 bigconst(A) ，它的行为类似于 guard 语句。所以把它扔掉。
然后接下来的事情是 R #= 0b0000 + (A << 4) 按预期工作但遇到问题，它无法按预期工作，
?- X #= 4 << 4.
X = 64.
?- 64 #= X << 4.
64#=X<<4.
反之亦然
B #= A >> 4.
也按预期工作，也遇到同样的问题。
?- X #= 64 >> 4.
X = 4.
?- 4 #= X >> 4.
4#=X>>4.
所以我尝试使用 in/2 添加一些约束但没有用，然后我意识到我已经拥有所有需要的约束并且它们起作用了。
asm(instruction('ADD', [A]), R) :-
R #= 0b0000 + (A << 4),
A #= (R - 0b0000) >> 4.
用法示例
?- asm(instruction('ADD', [5]), R).
R = 80.
?- asm(I,80).
I = instruction('ADD', [5]).
为了表明它不是一击奇观。
asm(instruction('SUB', [A]), R) :-
R #= 0b0001 + (A << 4),
A #= (R - 0b0001) >> 4.
用法示例
?- asm(instruction('SUB', [5]), R).
R = 81.
?- asm(I,81).
I = instruction('SUB', [5]).
Is this a bug in my program or a bug in Prolog? How would I fix this?
这是您正在使用的顶层的可用性错误。如果您非常仔细观察，您可能会发现一个小提示：
81#=_42146<<4 .
^ SPACE
这个微小的 space 意思是：请注意不止这个答案。事实上，有两个答案。第一个答案（来自 'ADD'）是假的，它不包含任何解决方案。只有第二个答案包含一个解决方案。
请注意，Prolog 主要产生答案而不是解决方案。这就是我们谈论 答案替换 的原因。答案和解决方案之间的关系很微妙。一个答案可能包含零到无限多个解决方案。
那么为什么 Prolog 不直接生成解决方案呢？
首先，对于非常无效的无限解决方案。想一想 length(L,3)，它有一个答案，其中包含所有长度为 3 的列表以及任何可以想象的元素，因此有无限多的解决方案。比如L = [1,2,3]或者L = [bof, toto, machin-maschin]或者L = [louis_XVI, bernie, bernie]等等。在逻辑变量的帮助下，我们可以将这个无穷大的三元素列表折叠成以下答案：L = [_A,_B,_C]。这就是逻辑变量的威力！
这种力量也被用在约束中。但是伴随着这种力量而来的是很多责任和负担。毕竟，许多问题在一个方向上很容易计算，而在另一个方向上很难计算。你发现了这样一个问题。在这种情况下，可以考虑改进 clpfd 以轻松处理这种情况，但在一般情况下它是不可判定的。因此，有时根本就没有算法。在这种情况下，给出一个虚假的答案（不一致，Scheinlösung，解决方案空白）是系统可以做的最好的事情。或者，它可能会产生错误并中止整个计算。但这太恶心了。通常，我们可以忍受这种不一致。
以你的情况为例，如果你真的想确保解决方案存在，通过将它们标记出来从答案中删除约束！
?- asm(I,81), I = instruction(_,[R]).
I = instruction('ADD', [R]),
R in 0..1023,
81#=R<<4
; I = instruction('SUB', [R]),
R in 0..1023,
80#=R<<4.
?- asm(I,81), I = instruction(_,[R]), labeling([],[R]).
I = instruction('SUB', [5]),
R = 5
; false.
另一种方法是使约束更强，如@Guy-Coder 所示。这可能有效（然后它很好）但理解起来更复杂。并且在某些情况下也可能效率较低。这是一个真正的工程问题。在某些情况下，我们什么时候接受不一致作为更快解决方案的代价？
我在一个更大的代码库中遇到过这个问题，但将其缩减为一个最小的可重现示例。这是汇编程序的一些代码：
:- use_module(library(clpfd)).
bigconst(X) :- X #=< 0x3FF, X #>= 0.
asm(instruction('ADD', [A]), R) :-
bigconst(A),
R #= 0b0000 + (A << 4).
asm(instruction('SUB', [A]), R) :-
bigconst(A),
R #= 0b0001 + (A << 4).
组装的时候好像可以用：
?- asm(instruction('SUB', [5]), R).
R = 81.
但是反汇编的时候好像失败了:
?- asm(I, 81).
I = instruction('ADD', [_42146]),
_42146 in 0..1023,
81#=_42146<<4 .
这是我程序中的错误还是 Prolog 中的错误？我该如何解决这个问题？
当我找到答案时，大声笑。我用过很多奇怪的模式来解决问题，但这是我以前从未使用过的。一旦我看到它的工作，我就知道我有一个用于工具箱的闪亮新工具。
对于 CLP(FD) 问题，它们通常可以双向工作，这正是您想要的。您遇到的第一个问题是您有 bigconst(A) ，它的行为类似于 guard 语句。所以把它扔掉。
然后接下来的事情是 R #= 0b0000 + (A << 4) 按预期工作但遇到问题，它无法按预期工作，
?- X #= 4 << 4.
X = 64.
?- 64 #= X << 4.
64#=X<<4.
反之亦然
B #= A >> 4.
也按预期工作，也遇到同样的问题。
?- X #= 64 >> 4.
X = 4.
?- 4 #= X >> 4.
4#=X>>4.
所以我尝试使用 in/2 添加一些约束但没有用，然后我意识到我已经拥有所有需要的约束并且它们起作用了。
asm(instruction('ADD', [A]), R) :-
R #= 0b0000 + (A << 4),
A #= (R - 0b0000) >> 4.
用法示例
?- asm(instruction('ADD', [5]), R).
R = 80.
?- asm(I,80).
I = instruction('ADD', [5]).
为了表明它不是一击奇观。
asm(instruction('SUB', [A]), R) :-
R #= 0b0001 + (A << 4),
A #= (R - 0b0001) >> 4.
用法示例
?- asm(instruction('SUB', [5]), R).
R = 81.
?- asm(I,81).
I = instruction('SUB', [5]).
Is this a bug in my program or a bug in Prolog? How would I fix this?
这是您正在使用的顶层的可用性错误。如果您非常仔细观察，您可能会发现一个小提示：
81#=_42146<<4 .
^ SPACE
这个微小的 space 意思是：请注意不止这个答案。事实上，有两个答案。第一个答案（来自 'ADD'）是假的，它不包含任何解决方案。只有第二个答案包含一个解决方案。
请注意，Prolog 主要产生答案而不是解决方案。这就是我们谈论 答案替换 的原因。答案和解决方案之间的关系很微妙。一个答案可能包含零到无限多个解决方案。
那么为什么 Prolog 不直接生成解决方案呢？
首先，对于非常无效的无限解决方案。想一想 length(L,3)，它有一个答案，其中包含所有长度为 3 的列表以及任何可以想象的元素，因此有无限多的解决方案。比如L = [1,2,3]或者L = [bof, toto, machin-maschin]或者L = [louis_XVI, bernie, bernie]等等。在逻辑变量的帮助下，我们可以将这个无穷大的三元素列表折叠成以下答案：L = [_A,_B,_C]。这就是逻辑变量的威力！
这种力量也被用在约束中。但是伴随着这种力量而来的是很多责任和负担。毕竟，许多问题在一个方向上很容易计算，而在另一个方向上很难计算。你发现了这样一个问题。在这种情况下，可以考虑改进 clpfd 以轻松处理这种情况，但在一般情况下它是不可判定的。因此，有时根本就没有算法。在这种情况下，给出一个虚假的答案（不一致，Scheinlösung，解决方案空白）是系统可以做的最好的事情。或者，它可能会产生错误并中止整个计算。但这太恶心了。通常，我们可以忍受这种不一致。
以你的情况为例，如果你真的想确保解决方案存在，通过将它们标记出来从答案中删除约束！
?- asm(I,81), I = instruction(_,[R]).
I = instruction('ADD', [R]),
R in 0..1023,
81#=R<<4
; I = instruction('SUB', [R]),
R in 0..1023,
80#=R<<4.
?- asm(I,81), I = instruction(_,[R]), labeling([],[R]).
I = instruction('SUB', [5]),
R = 5
; false.
另一种方法是使约束更强，如@Guy-Coder 所示。这可能有效（然后它很好）但理解起来更复杂。并且在某些情况下也可能效率较低。这是一个真正的工程问题。在某些情况下，我们什么时候接受不一致作为更快解决方案的代价？