SWI Prolog 使用的是什么检查优化？
What occurs-check optimizations is SWI Prolog using?
The usual mathematical theory behind Logic Programming forbids the
creation of cyclic terms, dictating that an occurs-check should be
done each time a variable is unified with a term. Unfortunately, an
occurs-check would be so expensive as to render Prolog impractical as
a programming language.
但是，我 运行 these benchmarks（Prolog 的）在 SWI Prolog 中发现发生检查 (OC) 打开和关闭之间存在相当小的差异（小于 20%）：
OC 已关闭：:- set_prolog_flag(occurs_check, false). 在 .swiplrc（重新启动）
?- run_interleaved(10).
% 768,486,984 inferences, 91.483 CPU in 91.483 seconds (100% CPU, 8400298 Lips)
true.
?- run(1).
'Program' Time GC
================================
boyer 0.453 0.059
browse 0.395 0.000
chat_parser 0.693 0.000
crypt 0.481 0.000
fast_mu 0.628 0.000
flatten 0.584 0.000
meta_qsort 0.457 0.000
mu 0.523 0.000
nreverse 0.406 0.000
poly_10 0.512 0.000
prover 0.625 0.000
qsort 0.574 0.000
queens_8 0.473 0.000
query 0.494 0.000
reducer 0.595 0.000
sendmore 0.619 0.000
simple_analyzer 0.620 0.000
tak 0.486 0.000
zebra 0.529 0.000
average 0.534 0.003
true.
OC 开启：:- set_prolog_flag(occurs_check, true). 在 .swiplrc（重新启动）
?- run_interleaved(10).
% 853,189,814 inferences, 105.545 CPU in 105.580 seconds (100% CPU, 8083669 Lips)
true.
?- run(1).
'Program' Time GC
================================
boyer 0.572 0.060
browse 0.618 0.000
chat_parser 0.753 0.000
crypt 0.480 0.000
fast_mu 0.684 0.000
flatten 0.767 0.000
meta_qsort 0.659 0.000
mu 0.607 0.000
nreverse 0.547 0.000
poly_10 0.541 0.000
prover 0.705 0.000
qsort 0.660 0.000
queens_8 0.491 0.000
query 0.492 0.000
reducer 0.867 0.000
sendmore 0.629 0.000
simple_analyzer 0.757 0.000
tak 0.550 0.000
zebra 0.663 0.000
average 0.634 0.003
true.
这些基准是否不能代表现实世界的使用情况？ （我记得在某处读到它们被特别选择为“相当有代表性”）SWI Prolog 是否实施了一些优化技巧，而 SICStus 的人并不知道，这使得 OC 的成本很小？如果是这样，它们是否已发布？ （我从 90 年代找到了一堆关于这个的论文，但我不知道它们是否是最先进的）
这是一个测试用例，发生检查使时间加倍
执行查询。在此处使用此代码，以计算否定正常
形式。由于 (=)/2 位于规则的末尾，因此访问的化合物
变成二次方：
/* Variant 1 */
norm(A, R) :- var(A), !, R = pos(A).
norm((A+B), R) :- !, norm(A, C), norm(B, D), R = or(C,D).
norm((A*B), R) :- !, norm(A, C), norm(B, D), R = and(C,D).
Etc..
我们可以与此变体进行比较，其中 (=)/2 首先完成，而复合尚未实例化：
/* Variant 2 */
norm(A, R) :- var(A), !, R = pos(A).
norm((A+B), R) :- !, R = or(C,D), norm(A, C), norm(B, D).
norm((A*B), R) :- !, R = and(C,D), norm(A, C), norm(B, D).
Etc..
以下是 SWI-Prolog 8.3.19 的一些测量值。对于变体 1，将 occurs check flag 设置为 true 会使从 principia mathematica 转换一些命题公式所需的时间加倍：
/* Variant 1 */
/* occurs_check=false */
?- time((between(1,1000,_),test,fail;true)).
% 3,646,000 inferences, 0.469 CPU in 0.468 seconds (100% CPU, 7778133 Lips)
true.
/* occurs_check=true */
?- time((between(1,1000,_),test,fail;true)).
% 6,547,000 inferences, 0.984 CPU in 0.983 seconds (100% CPU, 6650921 Lips)
true.
另一方面，将 (=)/2 移到前面可以更好地改变图片：
/* Variant 2 */
/* occurs_check=false */
?- time((between(1,1000,_),test,fail;true)).
% 3,646,000 inferences, 0.453 CPU in 0.456 seconds (99% CPU, 8046345 Lips)
true.
/* occurs_check=true */
?- time((between(1,1000,_),test,fail;true)).
% 6,547,000 inferences, 0.703 CPU in 0.688 seconds (102% CPU, 9311289 Lips)
true.
开源：
否定范式，非尾递归
https://gist.github.com/jburse/7705ace654af0df6f4fdd12eee80aaec#file-norm-pl
非范式，尾递归
https://gist.github.com/jburse/7705ace654af0df6f4fdd12eee80aaec#file-norm2-pl
来自 Principia 的 193 个命题逻辑测试用例。
https://gist.github.com/jburse/7705ace654af0df6f4fdd12eee80aaec#file-principia-pl
主要优化使局部变量的统一成为常量操作。
许多abstract machines，如PLM、ZIP、WAM、VAM，都为逻辑变量提供了一种特殊情况，这些逻辑变量不能是某些结构的子项（称为局部变量）。与这些变量的统一根本不需要任何发生检查，因此可以是常量。
以这种方式，无需额外的发生检查即可“回传”大项。
如果没有这种优化，语法处理（用于解析给定列表）的开销会在标记数量上呈二次方增长。每次“输入列表”被交回（因此，从图形上讲，每次您在语法主体中的非终结符后穿过逗号），都需要扫描剩余的输入列表以查找该局部变量的出现。 （它比字符数的二次方更好，因为正则表达式大多是尾递归编码的）。
引入了此优化 2007 in 5.6.39。
令人惊讶的是，即使在像 tak 这样根本没有构建单一结构的情况下，您的测量结果也会显示开销。据我所知，SWI 5.6.39 中的发生检查统一 运行 比有理树统一（对于简单情况）快一点，因为（当时）不需要额外的设置。
仍有足够的空间进行更多的发生检查优化。但只有当人们确实使用此功能时，这些才会发生。至于SWI，在过去的13年里并没有发生太多事情。
但想想看：第一个 Prolog，称为 Prolog 0，默认情况下确实支持发生检查。但是从 Prolog I（“Marseille Prolog”）开始，只能找借口（比如你引用的那些）。至少，该标准没有通过仅定义 executions and requiring unify_with_occurs_check/2 and acyclic_term/1 来排除默认发生检查统一。现在，SWI、Tau 和 Scryer 等 Prologs 通过标志可选地提供它。
Joachim Beer 的 NEW_UNBOUND 标签在同一方向上进行了进一步优化，该标签避免了对某些堆变量的额外检查，但代价是更复杂的方案。看
重新审视发生检查问题。 JLP 5(3) 1988. 和 LNCS 404.
The usual mathematical theory behind Logic Programming forbids the creation of cyclic terms, dictating that an occurs-check should be done each time a variable is unified with a term. Unfortunately, an occurs-check would be so expensive as to render Prolog impractical as a programming language.
但是，我 运行 these benchmarks（Prolog 的）在 SWI Prolog 中发现发生检查 (OC) 打开和关闭之间存在相当小的差异（小于 20%）：
OC 已关闭：:- set_prolog_flag(occurs_check, false). 在 .swiplrc（重新启动）
?- run_interleaved(10).
% 768,486,984 inferences, 91.483 CPU in 91.483 seconds (100% CPU, 8400298 Lips)
true.
?- run(1).
'Program' Time GC
================================
boyer 0.453 0.059
browse 0.395 0.000
chat_parser 0.693 0.000
crypt 0.481 0.000
fast_mu 0.628 0.000
flatten 0.584 0.000
meta_qsort 0.457 0.000
mu 0.523 0.000
nreverse 0.406 0.000
poly_10 0.512 0.000
prover 0.625 0.000
qsort 0.574 0.000
queens_8 0.473 0.000
query 0.494 0.000
reducer 0.595 0.000
sendmore 0.619 0.000
simple_analyzer 0.620 0.000
tak 0.486 0.000
zebra 0.529 0.000
average 0.534 0.003
true.
OC 开启：:- set_prolog_flag(occurs_check, true). 在 .swiplrc（重新启动）
?- run_interleaved(10).
% 853,189,814 inferences, 105.545 CPU in 105.580 seconds (100% CPU, 8083669 Lips)
true.
?- run(1).
'Program' Time GC
================================
boyer 0.572 0.060
browse 0.618 0.000
chat_parser 0.753 0.000
crypt 0.480 0.000
fast_mu 0.684 0.000
flatten 0.767 0.000
meta_qsort 0.659 0.000
mu 0.607 0.000
nreverse 0.547 0.000
poly_10 0.541 0.000
prover 0.705 0.000
qsort 0.660 0.000
queens_8 0.491 0.000
query 0.492 0.000
reducer 0.867 0.000
sendmore 0.629 0.000
simple_analyzer 0.757 0.000
tak 0.550 0.000
zebra 0.663 0.000
average 0.634 0.003
true.
这些基准是否不能代表现实世界的使用情况？ （我记得在某处读到它们被特别选择为“相当有代表性”）SWI Prolog 是否实施了一些优化技巧，而 SICStus 的人并不知道，这使得 OC 的成本很小？如果是这样，它们是否已发布？ （我从 90 年代找到了一堆关于这个的论文，但我不知道它们是否是最先进的）
这是一个测试用例，发生检查使时间加倍 执行查询。在此处使用此代码，以计算否定正常 形式。由于 (=)/2 位于规则的末尾，因此访问的化合物 变成二次方：
/* Variant 1 */
norm(A, R) :- var(A), !, R = pos(A).
norm((A+B), R) :- !, norm(A, C), norm(B, D), R = or(C,D).
norm((A*B), R) :- !, norm(A, C), norm(B, D), R = and(C,D).
Etc..
我们可以与此变体进行比较，其中 (=)/2 首先完成，而复合尚未实例化：
/* Variant 2 */
norm(A, R) :- var(A), !, R = pos(A).
norm((A+B), R) :- !, R = or(C,D), norm(A, C), norm(B, D).
norm((A*B), R) :- !, R = and(C,D), norm(A, C), norm(B, D).
Etc..
以下是 SWI-Prolog 8.3.19 的一些测量值。对于变体 1，将 occurs check flag 设置为 true 会使从 principia mathematica 转换一些命题公式所需的时间加倍：
/* Variant 1 */
/* occurs_check=false */
?- time((between(1,1000,_),test,fail;true)).
% 3,646,000 inferences, 0.469 CPU in 0.468 seconds (100% CPU, 7778133 Lips)
true.
/* occurs_check=true */
?- time((between(1,1000,_),test,fail;true)).
% 6,547,000 inferences, 0.984 CPU in 0.983 seconds (100% CPU, 6650921 Lips)
true.
另一方面，将 (=)/2 移到前面可以更好地改变图片：
/* Variant 2 */
/* occurs_check=false */
?- time((between(1,1000,_),test,fail;true)).
% 3,646,000 inferences, 0.453 CPU in 0.456 seconds (99% CPU, 8046345 Lips)
true.
/* occurs_check=true */
?- time((between(1,1000,_),test,fail;true)).
% 6,547,000 inferences, 0.703 CPU in 0.688 seconds (102% CPU, 9311289 Lips)
true.
开源：
否定范式，非尾递归
https://gist.github.com/jburse/7705ace654af0df6f4fdd12eee80aaec#file-norm-pl
非范式，尾递归
https://gist.github.com/jburse/7705ace654af0df6f4fdd12eee80aaec#file-norm2-pl
来自 Principia 的 193 个命题逻辑测试用例。
https://gist.github.com/jburse/7705ace654af0df6f4fdd12eee80aaec#file-principia-pl
主要优化使局部变量的统一成为常量操作。
许多abstract machines，如PLM、ZIP、WAM、VAM，都为逻辑变量提供了一种特殊情况，这些逻辑变量不能是某些结构的子项（称为局部变量）。与这些变量的统一根本不需要任何发生检查，因此可以是常量。 以这种方式，无需额外的发生检查即可“回传”大项。
如果没有这种优化，语法处理（用于解析给定列表）的开销会在标记数量上呈二次方增长。每次“输入列表”被交回（因此，从图形上讲，每次您在语法主体中的非终结符后穿过逗号），都需要扫描剩余的输入列表以查找该局部变量的出现。 （它比字符数的二次方更好，因为正则表达式大多是尾递归编码的）。
引入了此优化 2007 in 5.6.39。 令人惊讶的是，即使在像 tak 这样根本没有构建单一结构的情况下，您的测量结果也会显示开销。据我所知，SWI 5.6.39 中的发生检查统一 运行 比有理树统一（对于简单情况）快一点，因为（当时）不需要额外的设置。
仍有足够的空间进行更多的发生检查优化。但只有当人们确实使用此功能时，这些才会发生。至于SWI，在过去的13年里并没有发生太多事情。
但想想看：第一个 Prolog，称为 Prolog 0，默认情况下确实支持发生检查。但是从 Prolog I（“Marseille Prolog”）开始，只能找借口（比如你引用的那些）。至少，该标准没有通过仅定义 unify_with_occurs_check/2 and acyclic_term/1 来排除默认发生检查统一。现在，SWI、Tau 和 Scryer 等 Prologs 通过标志可选地提供它。
Joachim Beer 的 NEW_UNBOUND 标签在同一方向上进行了进一步优化，该标签避免了对某些堆变量的额外检查，但代价是更复杂的方案。看 重新审视发生检查问题。 JLP 5(3) 1988. 和 LNCS 404.