我如何计算递归规则执行的递归次数？
How could I calculate the number of recursions that a recursive rule does?
我正在处理一个问题；我想计算我的代码的递归规则执行了多少次递归。
我的程序检查对象是否是计算机硬件的组件（通过组件（X，Y）谓词）。例如组件（计算机，主板）-> true。
它甚至检查对象不是直接组件而是另一个组件的子组件的情况。例如。子组件（计算机、内存）-> 真。 （因为内存是主板的组件，而主板是计算机的组件）
因为我的代码超过 400 行，所以我将只向您展示一些形式组件 (X,Y) 和规则子组件 (X,Y) 的谓词。
因此，一些谓词如下：
component(computer,case).
component(computer,power_supply).
component(computer,motherboard).
component(computer,storage_devices).
component(computer,expansion_cards).
component(case,buttons).
component(case,fans).
component(case,ribbon_cables).
component(case,cables).
component(motherboard,cpu).
component(motherboard,chipset).
component(motherboard,ram).
component(motherboard,rom).
component(motherboard,heat_sink).
component(cpu,chip_carrier).
component(cpu,signal_pins).
component(cpu,control_pins).
component(cpu,voltage_pins).
component(cpu,capacitors).
component(cpu,resistors).
等等....
我的规则是：
subcomponent(X,Z):- component(X,Z).
subcomponent(X,Z):- component(X,Y),subcomponent(Y,Z).
嗯，为了计算一个给定的分量X到给定的分量Y的分量的个数——也就是递归规则子分量(X,Y)的递归次数，我做了一些尝试失败的。但是，我在下面介绍它们：
i)
number_of_components(X,Y,N,T):- T is N+1, subcomponent(X,Y).
number_of_components(X,Y,N,T):- M is N+1, subcomponent(X,Z), number_of_components(Z,Y,M,T).
在这种情况下，我得到这个错误："ERROR: is/2: Arguments are not sufficiently instantiated"。
ii)
number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L),
length(L,N),
write(N).
在这种情况下，我得到的结果是 1 或 11，在这个数字之后是真的，仅此而已。一点逻辑都没有！
iii)
count_elems_acc([], Total, Total).
count_elems_acc([Head|Tail], Sum, Total) :-
Count is Sum + 1,
count_elems_acc(Tail, Count, Total).
number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L),
count_elems_acc(L,0,Total),
write(Total).
在这种情况下，根据我的知识库，我得到的结果数字是不正确的。（或者我错误地翻译了它们——因为这种方式似乎有一些逻辑）
那么，我做错了什么，我应该写什么？
期待您的回答！
谓词的调用次数可能是一个困难的概念。我会说，使用您的系统提供的 the tools。
?- profile(number_of_components(computer,X)).
20===================================================================
Total time: 0.00 seconds
=====================================================================
Predicate Box Entries = Calls+Redos Time
=====================================================================
$new_findall_bag/0 1 = 1+0 0.0%
$add_findall_bag/1 20 = 20+0 0.0%
$free_variable_set/3 1 = 1+0 0.0%
...
so:count_elems_acc/3 1 = 1+0 0.0%
so:subcomponent/2 22 = 1+21 0.0%
so:component/2 74 = 42+32 0.0%
so:number_of_components/2 2 = 1+1 0.0%
另一方面，最重要的是子句变量之间的关系。这就是 Prolog 的本质。因此，请尝试阅读 - 比方说，用简单的英语 - 你的规则。
i) number_of_components(X,Y,N,T) N,T 与 X 有什么关系？我不能说。所以
?- leash(-all),trace.
?- number_of_components(computer,Y,N,T).
Call: (7) so:number_of_components(computer, _G1931, _G1932, _G1933)
Call: (8) _G1933 is _G1932+1
ERROR: is/2: Arguments are not sufficiently instantiated
Exception: (8) _G1933 is _G1932+1 ?
如果 Y 是 X 的 number_of_components，ii) number_of_components(X,Y) 就很有意义了。然后，
number_of_components(X,Y):- bagof(S,subcomponent(X,S),L), length(L,Y).
产生
?- number_of_components(computer,X).
X = 20.
或更好
?- aggregate(count, S^subcomponent(computer,S), N).
N = 20.
注意S的用法。它出现在目标中'existentially quantified'。即在证明目标的同时允许改变。
iii) count_elements_acc/3 或多或少相当于 length/2，因此结果（打印）似乎是正确的，但同样，它是 关系 在 X 和 Y 之间，你的最后一个条款未能成立。仅当目的是执行副作用时才应使用从子句打印...例如，调试...
您可以做的一件事是使用 call_with_depth_limit/3 进行迭代加深。您调用谓词（在本例中为 subcomponent/2）。你增加限制直到你得到一个结果，如果你得到一个结果，这个限制就是使用的最深的递归级别。您可以查看相关文档。
但是，您可以做一些更简单的事情。您的数据库可以表示为未加权的、有向的、无环图。因此，将您的整个数据库放在一个有向图中，如 library(ugraphs) 中所实现的那样，并找到它的传递闭包。在传递闭包中，组件的邻居是它的所有子组件。完成！
制作图表：
findall(C-S, component(C, S), Es),
vertices_edges_to_ugraph([], Es, Graph)
找到传递闭包：
transitive_closure(Graph, Closure)
并查找子组件：
neighbours(Component, Closure, Subcomponents)
Subcomponents 将是一个列表，您可以使用 length/2 获得它的长度。
编辑
一些随机的想法：在你的情况下，你的数据库似乎描述了一个图，根据定义，它既是有向的又是非循环的（组件与子组件的关系严格按照一种方式进行，对吧？）。这就是无需定义您自己遍历图形的原因，例如 this great question and answers 中很好地演示的示例。因此，您不需要定义自己的递归 subcomponent 谓词等
在使用数据库时将数据库表示为一个术语而不是将其保持为一个平面 table 的一个好处是编写操作它的谓词变得微不足道：你得到 Prolog 的回溯自由。由于 library(ugraph) 使用的图形的 S 表示非常适合 Prolog，因此您很可能最终也会得到一个更高效的程序。
我正在处理一个问题；我想计算我的代码的递归规则执行了多少次递归。
我的程序检查对象是否是计算机硬件的组件（通过组件（X，Y）谓词）。例如组件（计算机，主板）-> true。
它甚至检查对象不是直接组件而是另一个组件的子组件的情况。例如。子组件（计算机、内存）-> 真。 （因为内存是主板的组件，而主板是计算机的组件）
因为我的代码超过 400 行，所以我将只向您展示一些形式组件 (X,Y) 和规则子组件 (X,Y) 的谓词。
因此，一些谓词如下：
component(computer,case).
component(computer,power_supply).
component(computer,motherboard).
component(computer,storage_devices).
component(computer,expansion_cards).
component(case,buttons).
component(case,fans).
component(case,ribbon_cables).
component(case,cables).
component(motherboard,cpu).
component(motherboard,chipset).
component(motherboard,ram).
component(motherboard,rom).
component(motherboard,heat_sink).
component(cpu,chip_carrier).
component(cpu,signal_pins).
component(cpu,control_pins).
component(cpu,voltage_pins).
component(cpu,capacitors).
component(cpu,resistors).
等等....
我的规则是：
subcomponent(X,Z):- component(X,Z).
subcomponent(X,Z):- component(X,Y),subcomponent(Y,Z).
嗯，为了计算一个给定的分量X到给定的分量Y的分量的个数——也就是递归规则子分量(X,Y)的递归次数，我做了一些尝试失败的。但是，我在下面介绍它们：
i)
number_of_components(X,Y,N,T):- T is N+1, subcomponent(X,Y).
number_of_components(X,Y,N,T):- M is N+1, subcomponent(X,Z), number_of_components(Z,Y,M,T).
在这种情况下，我得到这个错误："ERROR: is/2: Arguments are not sufficiently instantiated"。
ii)
number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L),
length(L,N),
write(N).
在这种情况下，我得到的结果是 1 或 11，在这个数字之后是真的，仅此而已。一点逻辑都没有！
iii)
count_elems_acc([], Total, Total).
count_elems_acc([Head|Tail], Sum, Total) :-
Count is Sum + 1,
count_elems_acc(Tail, Count, Total).
number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L),
count_elems_acc(L,0,Total),
write(Total).
在这种情况下，根据我的知识库，我得到的结果数字是不正确的。（或者我错误地翻译了它们——因为这种方式似乎有一些逻辑）
那么，我做错了什么，我应该写什么？
期待您的回答！
谓词的调用次数可能是一个困难的概念。我会说，使用您的系统提供的 the tools。
?- profile(number_of_components(computer,X)).
20===================================================================
Total time: 0.00 seconds
=====================================================================
Predicate Box Entries = Calls+Redos Time
=====================================================================
$new_findall_bag/0 1 = 1+0 0.0%
$add_findall_bag/1 20 = 20+0 0.0%
$free_variable_set/3 1 = 1+0 0.0%
...
so:count_elems_acc/3 1 = 1+0 0.0%
so:subcomponent/2 22 = 1+21 0.0%
so:component/2 74 = 42+32 0.0%
so:number_of_components/2 2 = 1+1 0.0%
另一方面，最重要的是子句变量之间的关系。这就是 Prolog 的本质。因此，请尝试阅读 - 比方说，用简单的英语 - 你的规则。
i) number_of_components(X,Y,N,T) N,T 与 X 有什么关系？我不能说。所以
?- leash(-all),trace.
?- number_of_components(computer,Y,N,T).
Call: (7) so:number_of_components(computer, _G1931, _G1932, _G1933)
Call: (8) _G1933 is _G1932+1
ERROR: is/2: Arguments are not sufficiently instantiated
Exception: (8) _G1933 is _G1932+1 ?
ii) number_of_components(X,Y) 就很有意义了。然后，
number_of_components(X,Y):- bagof(S,subcomponent(X,S),L), length(L,Y).
产生
?- number_of_components(computer,X).
X = 20.
或更好
?- aggregate(count, S^subcomponent(computer,S), N).
N = 20.
注意S的用法。它出现在目标中'existentially quantified'。即在证明目标的同时允许改变。
iii) count_elements_acc/3 或多或少相当于 length/2，因此结果（打印）似乎是正确的，但同样，它是 关系 在 X 和 Y 之间，你的最后一个条款未能成立。仅当目的是执行副作用时才应使用从子句打印...例如，调试...
您可以做的一件事是使用 call_with_depth_limit/3 进行迭代加深。您调用谓词（在本例中为 subcomponent/2）。你增加限制直到你得到一个结果，如果你得到一个结果，这个限制就是使用的最深的递归级别。您可以查看相关文档。
但是，您可以做一些更简单的事情。您的数据库可以表示为未加权的、有向的、无环图。因此，将您的整个数据库放在一个有向图中，如 library(ugraphs) 中所实现的那样，并找到它的传递闭包。在传递闭包中，组件的邻居是它的所有子组件。完成！
制作图表：
findall(C-S, component(C, S), Es),
vertices_edges_to_ugraph([], Es, Graph)
找到传递闭包：
transitive_closure(Graph, Closure)
并查找子组件：
neighbours(Component, Closure, Subcomponents)
Subcomponents 将是一个列表，您可以使用 length/2 获得它的长度。
编辑
一些随机的想法：在你的情况下，你的数据库似乎描述了一个图，根据定义，它既是有向的又是非循环的（组件与子组件的关系严格按照一种方式进行，对吧？）。这就是无需定义您自己遍历图形的原因，例如 this great question and answers 中很好地演示的示例。因此，您不需要定义自己的递归 subcomponent 谓词等
在使用数据库时将数据库表示为一个术语而不是将其保持为一个平面 table 的一个好处是编写操作它的谓词变得微不足道：你得到 Prolog 的回溯自由。由于 library(ugraph) 使用的图形的 S 表示非常适合 Prolog，因此您很可能最终也会得到一个更高效的程序。