Prolog 递归和变量
Prolog Recursion and Variables
我有这个插入排序，可以在 Prolog 中按降序对列表进行排序，它有效：
insert(X,[],[X]).
insert(X, [Y|Tail], [X,Y|Tail]):- X > Y, !.
insert(X, [Y|Tail], [Y|NTail]):- insert(X, Tail, NTail).
ins_sort([], []).
ins_sort([X|Tail], Sorted):- ins_sort(Tail, STail), insert(X, STail, Sorted).
我在 SWISH 上 运行 它并试图通过以下跟踪了解它的功能：
Call:ins_sort([1, 2, 3, 4, 5], _12162)
Call:ins_sort([2, 3, 4, 5], _12358)
Call:ins_sort([3, 4, 5], _12358)
Call:ins_sort([4, 5], _12358)
Call:ins_sort([5], _12358)
Call:ins_sort([], _12358)
Exit:ins_sort([], [])
Call:insert(5, [], _12360)
Exit:insert(5, [], [5])
Exit:ins_sort([5], [5])
Call:insert(4, [5], _12366)
Call:4>5
Fail:4>5
Redo:insert(4, [5], _12370)
Call:insert(4, [], _12282)
Exit:insert(4, [], [4])
Exit:insert(4, [5], [5, 4])
Exit:ins_sort([4, 5], [5, 4])
Call:insert(3, [5, 4], _12378)
Call:3>5
Fail:3>5
Redo:insert(3, [5, 4], _12382)
Call:insert(3, [4], _12294)
Call:3>4
Fail:3>4
Redo:insert(3, [4], _12294)
Call:insert(3, [], _12300)
Exit:insert(3, [], [3])
Exit:insert(3, [4], [4, 3])
Exit:insert(3, [5, 4], [5, 4, 3])
Exit:ins_sort([3, 4, 5], [5, 4, 3])
Call:insert(2, [5, 4, 3], _12396)
Call:2>5
Fail:2>5
Redo:insert(2, [5, 4, 3], _12400)
Call:insert(2, [4, 3], _12312)
Call:2>4
Fail:2>4
Redo:insert(2, [4, 3], _12312)
Call:insert(2, [3], _12318)
Call:2>3
Fail:2>3
Redo:insert(2, [3], _12318)
Call:insert(2, [], _12324)
Exit:insert(2, [], [2])
Exit:insert(2, [3], [3, 2])
Exit:insert(2, [4, 3], [4, 3, 2])
Exit:insert(2, [5, 4, 3], [5, 4, 3, 2])
Exit:ins_sort([2, 3, 4, 5], [5, 4, 3, 2])
Call:insert(1, [5, 4, 3, 2], _12162)
Call:1>5
Fail:1>5
Redo:insert(1, [5, 4, 3, 2], _12162)
Call:insert(1, [4, 3, 2], _12336)
Call:1>4
Fail:1>4
Redo:insert(1, [4, 3, 2], _12336)
Call:insert(1, [3, 2], _12342)
Call:1>3
Fail:1>3
Redo:insert(1, [3, 2], _12342)
Call:insert(1, [2], _12348)
Call:1>2
Fail:1>2
Redo:insert(1, [2], _12348)
Call:insert(1, [], _12354)
Exit:insert(1, [], [1])
Exit:insert(1, [2], [2, 1])
Exit:insert(1, [3, 2], [3, 2, 1])
Exit:insert(1, [4, 3, 2], [4, 3, 2, 1])
Exit:insert(1, [5, 4, 3, 2], [5, 4, 3, 2, 1])
Exit:ins_sort([1, 2, 3, 4, 5], [5, 4, 3, 2, 1])
一旦超过第一个 "Exit"，我就会迷路。我理解所有的递归调用，直到我们到达一个空列表，由于另一个事实停止递归调用并开始返回，但是为什么在第 7 行第一次退出后未定义的 STail 变成空列表 []插入调用？
ins_sort([], []) 的出口将 STail 设置为空集 []，这是否意味着事实的最后一个参数是 return 值或其他内容？
Prolog 使用统一和模式 matching.You 正在删除 Head 并使用 tail 再次调用谓词，这会不断删除 Head 并尝试在每次调用后找到匹配项，稍后您会得到一个空列表，所以prolog 在您的文件中搜索匹配项，此时它找到了匹配项 ins_sort([], []).
在第 6 次调用时，您有 Call:ins_sort([], _12358)，其中 _12358 是一个变量，该变量将从 ns_sort([], []). 中获取值，这是事实。它只是意味着如果你在 ns_sort 中有一个空列表和一个变量然后设置该变量也等于空列表，如果你有所有其他 "terms" 匹配，变量将被实例化为任何东西。
通过学习回溯可以很容易地理解Prolog，回溯是一种算法所以prolog self是一种算法。
我认为这里的问题是您在理解递归过程中变量发生了什么时遇到了一些困难。举个简单的例子：
count([], 0).
count([X|Xs], N) :- count(Xs, N0), succ(N0, N).
当我调用 count([a,b], N) 时会发生什么：
count([a, b], N)
+-> count([b], N)
进入count([a,b], N)后我们要做的第一件事是递归调用count/2。当 Prolog 重新输入计数时，我们突然有了 X 和 Xs 的一组新绑定。在外部调用中，X=a 和 Xs=[b]，但在内部调用中，X=b 和 Xs=[]。然后会有第三次内部调用，它以 Xs 值 [] 开始。这对应于此跟踪的前三行：
Call: (8) count([a, b], _8636) ? creep
Call: (9) count([b], _8866) ? creep
Call: (10) count([], _8866) ? creep
此处跟踪器告诉您的是 "I am trying to enter this predicate with these values and variables." 请注意，在第一次和第二次调用之间，变量实际上发生了 N 的变化。
现在，您会注意到 [] 不能匹配第二个子句，只能匹配第一个。第一个没有主体，但它确实建立了绑定。所以跟踪的下一行将反映：
Exit: (10) count([], 0) ? creep
看到旁边的数字了吗？这告诉你调用堆栈的深度。使用数字代替直观显示嵌套很方便，因为最终我们的调用堆栈会变得很深！
现在我们有了变量的值，它将继续到我们所在的子句中的下一个表达式：
Call: (10) succ(0, _8866) ? creep
Exit: (10) succ(0, 1) ? creep
嵌套级别上升一级但立即解决；这对于像 succ/2 这样的内置插件来说是正常的。现在让我们看看跟踪的其余部分：
Exit: (9) count([b], 1) ? creep
Call: (9) succ(1, _8636) ? creep
Exit: (9) succ(1, 2) ? creep
Exit: (8) count([a, b], 2) ? creep
现在我们有了递归调用的绑定，我们可以在父调用中进入下一步，依此类推，直到整个调用被解析并得到 2。
让我们再看一遍，这次用嵌套代替数字：
[trace] ?- count([a,b],N).
Call: (8) count([a, b], _8636) ? creep
Call: (9) count([b], _8866) ? creep
Call: (10) count([], _8866) ? creep
Exit: (10) count([], 0) ? creep
Call: (10) succ(0, _8866) ? creep
Exit: (10) succ(0, 1) ? creep
Exit: (9) count([b], 1) ? creep
Call: (9) succ(1, _8636) ? creep
Exit: (9) succ(1, 2) ? creep
Exit: (8) count([a, b], 2) ? creep
N = 2.
这应该会使您自己的跟踪中发生的事情更容易理解。
痕迹太难了。重写通常要容易得多，尤其是像你在这里这样的确定性谓词。长变量名也太分散注意力了。与其阅读和记忆，不如简单地看一下：
insert(X, [], [X]). %1
insert(X, [Y|T], [X,Y|T] ):- X > Y, !. % X was indeed greater than Y: %2
% accept the solution and stop; %3
insert(X, [Y|T], [ Y|NT]):- insert(X, T, NT). % otherwise, insert into tail. %4
%5
ins_sort( [], []). % rule {1} %6
ins_sort( [X|T], S):- % rule {2} %7
ins_sort( T, ST), %8
insert( X, ST, %9
S). %10
让我们尝试使用更短的列表，
ins_sort([1, 2, 3], S) ? S. %11
= \ / %12
{2: [X1|T1]=[1,2,3] } / %13
ins_sort(T1, ST1), insert(X1, ST1, S). %14
= \ / %15
{2: [X2|T2]=T1=[2,3] } / %16
ins_sort(T2, ST2), insert(X2, ST2, ST1). %17
= \ / %18
{2: [X3|T3]=T2=[3] } / %19
ins_sort(T3, ST3), insert(X3, ST3, ST2). %20
= \ / %21
{1: T3=[] ST3=[] }. %22
然后我们沿着 V 形轨迹从左上角向下到中间，结束递归直到我们到达基本情况，然后向上和向右展开递归并构建结果在我们从基本案例返回的路上，as usual。因此我们着手建立，自下而上，
ST3 = []. %22
insert( {X3=3}, {ST3=[]}, ST2 ):- ST2 = [3]. %20
insert( {X2=2}, {ST2=[3]}, ST1 ):- ST1 = [3,2]. %17
insert( {X1=1}, {ST1=[3,2]}, S ):- S = [3,2,1]. %14
就是这样。
我有这个插入排序，可以在 Prolog 中按降序对列表进行排序，它有效：
insert(X,[],[X]).
insert(X, [Y|Tail], [X,Y|Tail]):- X > Y, !.
insert(X, [Y|Tail], [Y|NTail]):- insert(X, Tail, NTail).
ins_sort([], []).
ins_sort([X|Tail], Sorted):- ins_sort(Tail, STail), insert(X, STail, Sorted).
我在 SWISH 上 运行 它并试图通过以下跟踪了解它的功能：
Call:ins_sort([1, 2, 3, 4, 5], _12162)
Call:ins_sort([2, 3, 4, 5], _12358)
Call:ins_sort([3, 4, 5], _12358)
Call:ins_sort([4, 5], _12358)
Call:ins_sort([5], _12358)
Call:ins_sort([], _12358)
Exit:ins_sort([], [])
Call:insert(5, [], _12360)
Exit:insert(5, [], [5])
Exit:ins_sort([5], [5])
Call:insert(4, [5], _12366)
Call:4>5
Fail:4>5
Redo:insert(4, [5], _12370)
Call:insert(4, [], _12282)
Exit:insert(4, [], [4])
Exit:insert(4, [5], [5, 4])
Exit:ins_sort([4, 5], [5, 4])
Call:insert(3, [5, 4], _12378)
Call:3>5
Fail:3>5
Redo:insert(3, [5, 4], _12382)
Call:insert(3, [4], _12294)
Call:3>4
Fail:3>4
Redo:insert(3, [4], _12294)
Call:insert(3, [], _12300)
Exit:insert(3, [], [3])
Exit:insert(3, [4], [4, 3])
Exit:insert(3, [5, 4], [5, 4, 3])
Exit:ins_sort([3, 4, 5], [5, 4, 3])
Call:insert(2, [5, 4, 3], _12396)
Call:2>5
Fail:2>5
Redo:insert(2, [5, 4, 3], _12400)
Call:insert(2, [4, 3], _12312)
Call:2>4
Fail:2>4
Redo:insert(2, [4, 3], _12312)
Call:insert(2, [3], _12318)
Call:2>3
Fail:2>3
Redo:insert(2, [3], _12318)
Call:insert(2, [], _12324)
Exit:insert(2, [], [2])
Exit:insert(2, [3], [3, 2])
Exit:insert(2, [4, 3], [4, 3, 2])
Exit:insert(2, [5, 4, 3], [5, 4, 3, 2])
Exit:ins_sort([2, 3, 4, 5], [5, 4, 3, 2])
Call:insert(1, [5, 4, 3, 2], _12162)
Call:1>5
Fail:1>5
Redo:insert(1, [5, 4, 3, 2], _12162)
Call:insert(1, [4, 3, 2], _12336)
Call:1>4
Fail:1>4
Redo:insert(1, [4, 3, 2], _12336)
Call:insert(1, [3, 2], _12342)
Call:1>3
Fail:1>3
Redo:insert(1, [3, 2], _12342)
Call:insert(1, [2], _12348)
Call:1>2
Fail:1>2
Redo:insert(1, [2], _12348)
Call:insert(1, [], _12354)
Exit:insert(1, [], [1])
Exit:insert(1, [2], [2, 1])
Exit:insert(1, [3, 2], [3, 2, 1])
Exit:insert(1, [4, 3, 2], [4, 3, 2, 1])
Exit:insert(1, [5, 4, 3, 2], [5, 4, 3, 2, 1])
Exit:ins_sort([1, 2, 3, 4, 5], [5, 4, 3, 2, 1])
一旦超过第一个 "Exit"，我就会迷路。我理解所有的递归调用，直到我们到达一个空列表，由于另一个事实停止递归调用并开始返回，但是为什么在第 7 行第一次退出后未定义的 STail 变成空列表 []插入调用？
ins_sort([], []) 的出口将 STail 设置为空集 []，这是否意味着事实的最后一个参数是 return 值或其他内容？
Prolog 使用统一和模式 matching.You 正在删除 Head 并使用 tail 再次调用谓词，这会不断删除 Head 并尝试在每次调用后找到匹配项，稍后您会得到一个空列表，所以prolog 在您的文件中搜索匹配项，此时它找到了匹配项 ins_sort([], []).
在第 6 次调用时，您有 Call:ins_sort([], _12358)，其中 _12358 是一个变量，该变量将从 ns_sort([], []). 中获取值，这是事实。它只是意味着如果你在 ns_sort 中有一个空列表和一个变量然后设置该变量也等于空列表，如果你有所有其他 "terms" 匹配，变量将被实例化为任何东西。
通过学习回溯可以很容易地理解Prolog，回溯是一种算法所以prolog self是一种算法。
我认为这里的问题是您在理解递归过程中变量发生了什么时遇到了一些困难。举个简单的例子：
count([], 0).
count([X|Xs], N) :- count(Xs, N0), succ(N0, N).
当我调用 count([a,b], N) 时会发生什么：
count([a, b], N)
+-> count([b], N)
进入count([a,b], N)后我们要做的第一件事是递归调用count/2。当 Prolog 重新输入计数时，我们突然有了 X 和 Xs 的一组新绑定。在外部调用中，X=a 和 Xs=[b]，但在内部调用中，X=b 和 Xs=[]。然后会有第三次内部调用，它以 Xs 值 [] 开始。这对应于此跟踪的前三行：
Call: (8) count([a, b], _8636) ? creep
Call: (9) count([b], _8866) ? creep
Call: (10) count([], _8866) ? creep
此处跟踪器告诉您的是 "I am trying to enter this predicate with these values and variables." 请注意，在第一次和第二次调用之间，变量实际上发生了 N 的变化。
现在，您会注意到 [] 不能匹配第二个子句，只能匹配第一个。第一个没有主体，但它确实建立了绑定。所以跟踪的下一行将反映：
Exit: (10) count([], 0) ? creep
看到旁边的数字了吗？这告诉你调用堆栈的深度。使用数字代替直观显示嵌套很方便，因为最终我们的调用堆栈会变得很深！
现在我们有了变量的值，它将继续到我们所在的子句中的下一个表达式：
Call: (10) succ(0, _8866) ? creep
Exit: (10) succ(0, 1) ? creep
嵌套级别上升一级但立即解决；这对于像 succ/2 这样的内置插件来说是正常的。现在让我们看看跟踪的其余部分：
Exit: (9) count([b], 1) ? creep
Call: (9) succ(1, _8636) ? creep
Exit: (9) succ(1, 2) ? creep
Exit: (8) count([a, b], 2) ? creep
现在我们有了递归调用的绑定，我们可以在父调用中进入下一步，依此类推，直到整个调用被解析并得到 2。
让我们再看一遍，这次用嵌套代替数字：
[trace] ?- count([a,b],N).
Call: (8) count([a, b], _8636) ? creep
Call: (9) count([b], _8866) ? creep
Call: (10) count([], _8866) ? creep
Exit: (10) count([], 0) ? creep
Call: (10) succ(0, _8866) ? creep
Exit: (10) succ(0, 1) ? creep
Exit: (9) count([b], 1) ? creep
Call: (9) succ(1, _8636) ? creep
Exit: (9) succ(1, 2) ? creep
Exit: (8) count([a, b], 2) ? creep
N = 2.
这应该会使您自己的跟踪中发生的事情更容易理解。
痕迹太难了。重写通常要容易得多，尤其是像你在这里这样的确定性谓词。长变量名也太分散注意力了。与其阅读和记忆，不如简单地看一下：
insert(X, [], [X]). %1
insert(X, [Y|T], [X,Y|T] ):- X > Y, !. % X was indeed greater than Y: %2
% accept the solution and stop; %3
insert(X, [Y|T], [ Y|NT]):- insert(X, T, NT). % otherwise, insert into tail. %4
%5
ins_sort( [], []). % rule {1} %6
ins_sort( [X|T], S):- % rule {2} %7
ins_sort( T, ST), %8
insert( X, ST, %9
S). %10
让我们尝试使用更短的列表，
ins_sort([1, 2, 3], S) ? S. %11
= \ / %12
{2: [X1|T1]=[1,2,3] } / %13
ins_sort(T1, ST1), insert(X1, ST1, S). %14
= \ / %15
{2: [X2|T2]=T1=[2,3] } / %16
ins_sort(T2, ST2), insert(X2, ST2, ST1). %17
= \ / %18
{2: [X3|T3]=T2=[3] } / %19
ins_sort(T3, ST3), insert(X3, ST3, ST2). %20
= \ / %21
{1: T3=[] ST3=[] }. %22
然后我们沿着 V 形轨迹从左上角向下到中间，结束递归直到我们到达基本情况，然后向上和向右展开递归并构建结果在我们从基本案例返回的路上，as usual。因此我们着手建立，自下而上，
ST3 = []. %22
insert( {X3=3}, {ST3=[]}, ST2 ):- ST2 = [3]. %20
insert( {X2=2}, {ST2=[3]}, ST1 ):- ST1 = [3,2]. %17
insert( {X1=1}, {ST1=[3,2]}, S ):- S = [3,2,1]. %14
就是这样。