《The Craft of Prolog》笔记

在这里我把书里比较有用的技巧做一下记录吧。

1.4.2中讲了尾递归优化。

比如要求一个列表的长度，第一种代码是这样：

len([], 0).
len([_|Tail], N):-
    len(Tail, M),
    N is M + 1.

它没什么不对，但运行时会生成栈框架塔，占用大量空间。每次往下递归时，自然会?生成新的一个列表和变量。但问题在于，这个代码会使得，直到列表清空、最深层的递归返回0，之前的这些列表及对应的值才能进行逐渐返回，依次得到释放。比如，一个列表为[1, 2, 3]，将其导入，对应的长度为N，然后开始第一次层递归，关联了新的列表[2, 3]及其对应的长度N0，N＝N0＋1；进行第二层递归，导入列表[2, 3]，关联新的列表[3]，N0＝N1＋1；进行第三层递归，导入列表[3]，关联新的列表[]，N1＝N2＋1；进行第四层递归，导入[]，符合第1个语句，N2确定为0，递归终止。至此，之前生成的列表和对应的长度都还存在。随后，进行返回，列表[3]对应的长度为1，列表[2, 3]对应的是2，列表[1, 2, 3]对应的是3，这才逐渐释放。

而第二种代码是这样：

len(List, Length):-
    len(List, 0, Length).

len([], N, N).
len([_|L], N0, N):-
    N1 is N0 + 1,
    len(L, N1, N).

首先，传入len(List, Length)，会变成len(List, 0, Length)，然后后者如果不为空，会与len([_|L], N0, N)进行绑定，Length等同于N。然后进行递归，N0从0开始逐渐增大，而在完成最里层的递归前，所有层的递归N（Length）一直是占用同一个未知变量。当列表清空时，会与len([], N, N).语句绑定，将中间的N的值绑定给右边的N，从而Length得到确定。比如列表[1, 2, 3]，一开始得到len([1, 2, 3], 0, Length)，第一次递归后，得到得到len([2, 3], 1, Length)，第二次递归，得到len([3], 2, Length)，第三次得到第二次递归，得到len([], 3, Length)，最后调用len([], N, N)，递归结束，Length的长度与中间的N绑定，得以确定。

第一种代码，即使运行完最里层的递归依然没有结束，还得依次从里往外返回值。但第二种代码，它每次往下递归都能得出确切的值，当运行完最里层的递归时，最外面层的未知变量同时得以确定。只用跑一趟。