适用于大数的 positive_integer/1 谓词

Question

在我的 Prolog 启发语言中 Brachylog, there is the possibility to label CLP(FD)-equivalent variables that have potentially infinite domains. The code that does this labelization can be found here（感谢 Markus Triska @mat）。

此谓词要求存在谓词 positive_integer/1，它必须具有以下行为：

?- positive_integer(X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
…

这在我们当前的解决方案中是这样实现的：

positive_integer(N) :- length([_|_], N).

我发现这有两个问题：

这很快就会变慢：

?- time(positive_integer(100000)).
% 5 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)

?- time(positive_integer(1000000)).
% 5 inferences, 0.000 CPU in 0.008 seconds (0% CPU, Infinite Lips)

?- time(positive_integer(10000000)).
% 5 inferences, 0.062 CPU in 0.075 seconds (83% CPU, 80 Lips)

这最终 returns 一个 Out of global stack 数字有点太大的错误：
```
?- positive_integer(100000000).
ERROR: Out of global stack
```

这显然是因为Prolog需要实例化列表，如果列表的长度很大就不好了。

我们如何改进这个谓词，使其即使对于非常大的数字也能以相同的行为工作？

Answer 1

因为 "Brachylog's interpreter is entirely written in Prolog" 表示 SWI-Prolog，您可以使用 between/3 并将第二个参数绑定到 inf。

将您的 positive_integer 与

进行比较

positive_integer_b(X):- between(1,inf,X).

在我的机器上测试：

?- time(positive_integer(10000000)).
% 5 inferences, 0.062 CPU in 0.072 seconds (87% CPU, 80 Lips)
true.
9 ?- time(positive_integer_b(10000000)).
% 2 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
true.

并显示 "Out of global stack":

13 ?- time(positive_integer(100000000)).
% 5 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
ERROR: Out of global stack

14 ?- time(positive_integer_b(100000000)).
% 2 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
true.

虽然我不认为 between is pure prolog。

Answer 2

如果您希望您的代码也可以在其他系统上运行，请考虑：

positive_integer(N) :-
   (  nonvar(N), % strictly not needed, but clearer
      integer(N),
      N > 0
   -> true
   ;  length([_|_], N)
   ).

此版本产生的错误与您的第一次尝试完全相同。

您确实发现了当前 length/2 实施中的一些弱点。理想情况下，像 length([_|_], 1000000000000000) 这样的目标会花费一些时间，但至少不会消耗超过常量内存。另一方面，我不太确定这是否值得优化。毕竟，我没有看到解决此类情况的运行时问题的简单方法。

请注意，SWI-Prolog 中 between/3 的版本是高度特定于 SWI 的。它使终止参数变得更加复杂。在 SICStus 等其他系统中，无论参数如何，您都可以肯定地知道 between/3 正在终止。在 SWI 中，您必须证明不会遇到原子 inf，这增加了举证义务的负担。

Answer 3

没有 between/3，并且符合 ISO（我认为）

positive_integer(1).
positive_integer(X) :-
 var(X),
 positive_integer(Y),
 X is Y + 1.
positive_integer(X) :-
 integer(X),
 X > 0.

Answer 4

已经发布了很多好的想法，它们在不同程度上发挥了作用。

附加测试用例

@vmg 有正确的直觉：between/3 不能很好地与约束混合。为了看到这一点，我想使用以下查询作为额外的基准：

?- X #> 10^30, positive_integer(X).

解决方案

考虑到测试用例，我建议以下解决方案：

positive_integer(I) :-
        I #> 0,
        (   var(I) ->
            fd_inf(I, Inf),
            (   I #= Inf
            ;   I #\= Inf,
                positive_integer(I)
            )
        ;   true
        ).

关键思想是使用 CLP(FD) 反射谓词 fd_inf/2 来推理最小元素变量的域。这是将解决方案移植到更多 Prolog 系统时唯一需要更改的谓词。例如，在 SICStus Prolog 中，谓词称为 fd_min/2.

主要特点

可移植到多个 Prolog 系统，变化很小
快速在显示的案例中
在上面的测试用例中也有效
通告并使用 CLP(FD) 约束的全部功能。

当然很清楚哪一点最重要。

示例查询

创造 无中生有:

?- positive_integer(X).
X = 1 ;
X = 2 ;
X = 3 .

固定整数：

?- X #= 12^42, time(positive_integer(X)).
% 4 inferences, 0.000 CPU in 0.000 seconds (68% CPU, 363636 Lips)
X = 2116471057875484488839167999221661362284396544.

约束整数：

?- X #> 10^30, time(positive_integer(X)).
% 124 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 3647059 Lips)
X = 1000000000000000000000000000001 ;
% 206 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 2367816 Lips)
X = 1000000000000000000000000000002 ;
% 204 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 2428571 Lips)
X = 1000000000000000000000000000003 .

其他评论

首先，请务必查看 Code Golf 上的 Brachylog and the latest Brachylog solutions。由于 Julien 的努力，一种受 Prolog 启发的语言现在越来越多地托管一些发布在那里的最简洁和优雅的程序。朱利安干得好！
请避免使用 between/3 的特定实现异常：这些会破坏谓词的重要语义属性并且不能移植到其他系统。
如果忽略(2)，请使用infinite代替inf。在 CLP(FD) 的上下文中，inf 表示整数集的 infimum，它正好是正数的 opposite无限.
在 CLP(FD) 的上下文中，我建议使用 CLP(FD) 约束 而不是 between/3 的 和其他谓词 不考虑约束.
事实上，我建议使用 CLP(FD) 约束 而不是 的 all 低级谓词对整数的推理。这最多可以使您的程序更通用，永远不会更具体。

非常感谢您对此问题的关注和发布的解决方案！我希望您发现上面的测试用例对您的变体有用，并找到在您的版本中考虑 CLP(FD) 约束的方法，以便它们运行更快，我们都可以给它们投票！

适用于大数的 positive_integer/1 谓词

A positive_integer/1 predicate that works for big numbers

prolog

integer

clpfd

附加测试用例

解决方案

主要特点

示例查询

其他评论