Prolog递归和变量-Java 学习之路

我有这个插入排序在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])

一旦超出第一个“退出”，我就迷路了 . 我理解所有递归调用，直到我们到达一个空列表，由于其他事实而停止递归调用并开始返回，但为什么在第7行第一次退出后，未定义的STail成为空列表[] in插入电话？

ins_sort（[]，[]）的退出是否将STail设置为空set []并且这是否意味着事实的最后一个参数是返回值还是什么？

3 回答

1
我认为这里的问题是你在理解递归过程中变量的变化时遇到了一些困难 . 我们来看一个简化的案例：
```
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
```
跟踪器在这里告诉你的是“我试图用这些值和变量输入这个谓词 . ”请注意，在第一次和第二次调用之间，变量实际上已更改为N.

现在，您会注意到 [] 与第二个子句不匹配，只是第一个 . 第一个没有身体，但确实 Build 了绑定 . 因此，跟踪的下一行将反映出：
```
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.
```
这应该使您自己的跟踪中的内容更容易理解 .
回复于 2024-04-30T01:41:02+08:00

痕迹太难了 . 重写通常要容易得多，特别是像你在这里的确定性谓词一样 . 长变量名也太分散注意力了 . 而不是阅读和记忆，只是简单地看到它可能更容易：

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 . 因此，我们继续从下往上 Build ，

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

就是这样 .

回复于 2024-04-30T01:41:02+08:00

0

Prolog适用于统一和模式匹配 . 你正在删除Head并再次使用tail调用谓词，它会一直删除Head并尝试在每次调用后找到匹配项，稍后你会有一个空列表，所以prolog会搜索你的文件以获得匹配并且此时它找到一个匹配 ins_sort([], []). 在第6次调用时你有 Call:ins_sort([], _12358) 其中 _12358 是一个变量，这个变量将从 ns_sort([], []). 获得这是一个事实 . 它只是意味着如果你在ns_sort中有一个空列表，并且一个变量然后设置该变量也等于空列表，如果你有所有其他"terms"匹配，变量将被任何东西实例化 .

通过学习回溯可以很容易地理解Prolog，回溯是一种算法，因此prolog self是一种算法 .

回复于 2024-04-30T01:41:02+08:00

Prolog递归和变量

3 回答

相关问题