prolog - 适用于大数的 positive_integer/1 谓词

Question

在我的受 Prolog 启发的语言 Brachylog 中，有可能标记具有潜在无限域的 CLP(FD) 等效变量。可以在 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)

对于有点太大的数字，这最终会返回 Out of global stack 错误:

?- positive_integer(100000000).
ERROR: Out of global stack

这显然是因为 Prolog 需要实例化列表，如果它的长度很大，这很糟糕。

我们如何改进这个谓词，使其即使对非常大的数字也有效，具有相同的行为？

Answer 1

已经发布了许多好的想法，并且它们在不同程度上起作用。

附加测试用例

@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) 约束的全部功能。

当然，这些点中哪一点最重要是很清楚的。

示例查询

创造 ex nihilo :

?- 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 和最新的 Brachylog solutions。由于 Julien 的努力，受 Prolog 启发的语言现在越来越多地承载一些最简洁、最优雅的程序，这些程序发布在那里。很棒的工作朱利安!

请不要使用 between/3 的特定于实现的异常:这些会破坏谓词的重要语义属性，并且不能移植到其他系统。

如果您忽略 (2)，请使用 infinite 而不是 inf 。在 CLP(FD) 的上下文中，inf 表示整数集的 infimum ，它与正无穷大正好相反。

在 CLP(FD) 的上下文中，我建议使用 CLP(FD) 约束而不是 between/3 和其他不考虑约束的谓词。

事实上，我建议使用 CLP(FD) 约束而不是 所有 对整数进行推理的低级谓词。这最多可以使您的程序更通用，而不是更具体。

非常感谢您对这个问题和已发布的解决方案感兴趣!我希望您发现上面的测试用例对您的变体有用，并找到在您的版本中考虑 CLP(FD) 约束的方法，以便它们运行得更快，我们都可以为它们点赞!