Stack Trace Prolog Predicate

Question

我有一个非常简单的用Prolog编写的min函数，我不明白它是如何工作的。

代码：

min(E, [E]) :- write('case 1: '), write(E), nl. 
min(E, [E|L]) :- write('case 2: '), write(E), write(' '), write([E|L]), nl, min(F, L), E =< F. 
min(E, [F|L]) :- write('case 3: '), write(E), write(' '), write([F|L]), nl, min(E, L), E =< F. 

我们刚开始在课堂上使用Prolog的，我不明白它是如何计算的递归情况下，像这一个。我包括打印语句在此功能，看看发生了什么事情，我不明白这里的一些步骤：

10 ?- min(E, [2, 1]). 
case 2: 2 [2,1] 
case 1: 1 
case 2: 1 [1] 
case 3: _L164 [1] 
case 3: _G323 [2,1] 
case 1: 1 
E = 1 . 

我了解前两个电话，但我不明白的行之后会发生什么case 1: 1。为什么在第3行第2个案例min(E, [E|L])之后去了案例1，min(E, [E])？这从代码中的任何地方都没有。如果有人能够在前两次电话会议之后解释发生了什么，那会很好。我四处寻找一些解释，但我一直无法理解这里发生了什么。

Answer 1

为了解决这个问题，我们将播放序言解释器。 :)

min(E, [E]) :- 
    write('case 1: '), write(E), nl. 
min(E, [E|L]) :- 
    write('case 2: '), write(E), write(' '), write([E|L]), nl, 
    min(F, L), 
    E =< F. 
min(E, [F|L]) :- 
    write('case 3: '), write(E), write(' '), write([F|L]), nl, 
    min(E, L), 
    E =< F. 

我们做查询：

min(E, [2,1]). 

（A）序言从第一句话开始，min(E, [E])既然[2,1]不能[E]统一失败。然后，它进入下一个条款，min(E, [E|L])，并且能够通过统一E与2和L与[1]统一[2,1]与[E|L]，然后我们看到：

case 2: 2 [2,1] % This is E instantiated as 2, and [E|L] as [2|[1]] 

（B）的Prolog然后进行递归查询，min(F, [1]) 。从这里，它返回到子句列表顶部（在新的查询中，从顶部开始），并且能够通过统一F和1来统一第一个子句min(E, [E])中的变量。然后，我们看到：

case 1: 1 

（C）这个查询成功，回来它是从查询和遇到E =< F其中E是统一的2和F是统一的1条款。但E =< F将失败，因为1 =< 2是不正确的。此时，Prolog将回溯，然后重新尝试之前的递归查询，min(F, [1])。回想一下，查询已经执行了第一个子句并且成功了，所以现在在回溯时它会尝试第二个子句。它看起来统一min(F, [1])与min(E, [E|L])，并可以通过统一E与1和L与[]这样做。然后第2个执行，我们得到：

case 2: 1 [1] 

（d）我们现在是一个额外的呼叫深条款2.我们还没有完成第一个呢。因此，此新呼叫将查询min(F, [])（在此情况下记住L与[]统一）。您的谓词中没有与min(F, [])匹配的子句，因此它失败。因此，这种情况2查询的这个实例完全失败（通过writes回溯，不会在回溯时重新执行）。这是上面（C）的递归查询。 （E）由于情况2在（C）的递归调用中失败，Prolog继续通过执行第三个条款回溯并重新尝试，并且通过统一第一个条目并将min(E, [F|L])与min(F, [1])（注意：这些是“不同的”F） F与1,L与[]和E与第二个F统一（但没有实例化 - 没有赋值）。这里需要注意的是，在Prolog中，两个变量可以是统一的，但尚未分配一个值。由于第三条的头已经统一，案例3个执行，我们看到：

case 3: _L164 [1] % This is E (uninstantiated) and [F|L] ([1|[]]) 

的_L164出现，因为我们正在编写一个非实例变量。在这样的输出中，未经实例化的变量显示为生成的变量名称，后面跟着下划线（_）。

（F）因此壳体3和执行确实给min(E, L)递归调用，其中被E和非实例是L[]。此查询将失败，因为没有与min(_, [])匹配的子句。然后Prolog将从情况3回溯，然后从（C）到min(F, [1])的整个递归调用失败。 （G）请记住，我们在（C）中描述的情况2下从递归调用得到（F）。由于递归调用失败（如（D）至（F）中所述），Prolog通过回溯来恢复（C）中描述的情况2，失败情况2并继续前进至情况3.谓词的整个执行是原始查询，min(E, [2,1])。第三条款的标题为min(E, [F|L])，Prolog将第一条E与第二条E（未经实例化，但是）统一为F，2和L与[1]一致。我们现在看到：

case 3: _G323 [2,1] % This is E (uninstantiated) and [F|L] ([2|[1]]) 

（H）案例3个募集资金，但在min(E, [1])（已实例化L与[1]）递归查询从顶部再次启动时，第一条min(E, [E])和序言统一E与1和匹配该条的头相匹配。我们然后看到：

case 1: 1 

（I）情况1成功，回来壳体3，其进行和检查E =< F是1 =< 2（见unifications中（G）），这是Ť后悔。我们现在已经完全成功案例3！

我们完成了！与外壳3的成功（情况1如（A）中描述已经失败，和壳体2具有如（E）中描述的故障），原始查询已通过统一E与1成功，我们看到：

E = 1. 

当您在Prolog中执行查询时，它将从您正在查询的谓词的第一个子句开始，并依次尝试每个子句，直到找到一个成功的子句为止，然后它将声明成功。如果它们全部失败，那么当然，查询失败。在尝试每个子句的过程中，如果存在递归查询（调用），则该递归调用将从第一个子句开始。每个递归调用都是它自己对谓词的全面查询。因此，每次递归调用将从谓词的第一个子句开始，通过谓词的每个子句进行真实寻求。这是了解Prolog的一个重要原则，它有助于理解基本的递归行为。

关于跟踪的主题，代码中的write语句在显示谓词火灾的哪些子句方面做得很好。但是它们不显示子句中的哪些查询失败，这与了解在查询中发生的情况一样重要。因此，只有write声明可能会有点混淆。由@User建议的gtrace（或trace）命令将显示成功和失败的查询。这是一个很好的工具，用来查看条款中发生了什么，或许可以结合write语句来查看变量等。

Answer 2

您可以在SWI-Prolog中使用gtrace来跟踪评估。

10 -gtrace，min（E，[2,1]）。