4.1 - Recursion

WHAT IS RECURSION?

  1. A statement that refers to itself一个指代自身的陈述
  2. OR：一个句子中，相同的谓语(predicate)出现在头部和身体中
  3. 递归是计算机编程中的一种强大工具。

Example: Ancestors

什么是祖先？
• 父母parent
• 祖父母grandparent
• 曾祖父母great-grandparent
• 曾曾祖父母great-great-great-great
• 等等

1
2
ancestor(X,Y) :- X is directly above Y, in the family tree, by any number of generations.
(X在家族谱系中直接位于Y之上，无论经过多少代。)

我们如何向Prolog解释这个？

Brute Force Version

1
2
3
4
5
ancestor (X,Y):-parent (X,Y). 
ancestor (X,Y):-grandparent (X,Y). 
ancestor (X,Y):-greatGrandparent (X,Y). 
ancestor (X,Y):-parent (X,Z), greatGrandparent (Z,Y).
...

A Better Idea.更好的办法

1
2
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

"Your parent is your ancestor, and any ancestor of your ancestor is also your ancestor.”

你的父母是你的祖先，而你祖先的任何祖先也是你的祖先。

1
2
ancestor (X,Y):-parent (X,Y).<-BASE CASE 
ancestor (X,Y): parent (X,Z),ancestor (Z,Y). <-RECURSIVE CASE

How does it work?

1
?- ancestor (shmi,ben).

Prolog 查找atoms和condition
• ancestor(X,Y) :- parent(X,Y).
• ancestor(shmi,ben) :- parent(shmi,ben).
• 但这个结果为false
但还有另一个condition…

Second conditional

1
ancestor (shmi,ben) :- parent (shmi,Z), ancestor (Z,ben)

  • Z是谁？

  • 只有一个与parent(shmi,Z)可以unified

  • Z = anakin

  • 现在我们在寻找ancestor(anakin,ben)

Backchaining again…

  • Atom: ancestor(anakin,ben). (Not found)
  • First conditional: ancestor(anakin,ben) :- parent(anakin,ben).
  • This evaluates false

Second conditional

  • ancestor(shmi,ben) :- parent(shmi,Z),ancestor(Z,ben).
  • Who could Z be?
  • Only one thing unifies with parent(shmi,Z)
  • Z = anakin
  • So now we are looking for ancestor(anakin,ben)

Backchaining again…再次回溯

• Atom: ancestor(anakin,ben). (Not found)
• First conditional: ancestor(anakin,ben) :- parent(anakin,ben).
• This evaluates false

Infinite Recursion?无限递归

我们如何知道程序不会永远运行？

因为递归的情况结构良好。
• 在recursive case之前有一个base case
• 在recursive case中，parent (not recursive) 在ancestor (recursive)之前被evaluated。
• 每次程序递归时，它都会进入下一代（generations）。
• 知识库有有限数量的代（generations）。
• 因此，在有限的时间内，我们最终会到达base case或fail

More Formally更正式地

我们可以用数学证明递归程序会给我们需要的答案。
我们用数学归纳法来做这件事。(一个温和的版本)

Mathematical Induction数学归纳法

我们证明什么？
对于任何作为Y的direct ancestor的X，若X在family tree中位于Y上方k代，
我们的ancestor谓词对将返回true。
k为任意自然数（1, 2, …，直至无穷）

Base case

k的最小可能值为1。
如果k为1，parent(X,Y)会为true。
ancestor(X,Y) :- parent(X,Y)
就这样完成了！

避免死循环

1
2
3
ancestor(X,Y) :- parent(X,Y).

ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y)

1.Base case first, BEFORE recursive case(s)

（Base case 必须放在递归前面）

In a recursive case, non-recursive atoms BEFORE recursive ones

（递归规则中，非递归条件必须写在递归调用前）

ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y)

Prolog的运行顺序

1
2
3
4
?-parent(X,luke), \+ male(X).
X =padme
?- \+ male(X), parent(X,luke).
False

4.2 - Lists

​

有时我们需要一组非常相似但参数个数不同的谓词
例如，测试一组人彼此是否都不同。

1
2
3
uniq_person3(X,Y,Z) :- ...
uniq_person4(X,Y,Z,U) :- ...
uniq_person5(X,Y,Z,U,V) :- ...

如果我们能只写一个对任意数量的人都适用的谓词，那将容易得多，不论人数多或少。

1
uniq_people(L) :- ...

这种集合称为列表。

Lists

列表是对象（terms）的序列。
列表中的每一项称为一个元素(elemen)。
它们被放在方括号中并用逗号分隔。

1
[anna, karenina]
  • 一个包含两个元素的列表。第一个元素是 anna，第二个元素是 karenina。
1
[intro,to,programming, in, prolog]
  • 一个有五个元素的列表。
1
[1, 2, 3, 3, 2, 1]
  • 一个包含数字项的六元素列表。
  • 列表可能有重复的元素。
1
[]
  • 一个没有元素的列表。空列表。

Structured Lists

列表可以包含其他列表作为元素。

1
[[john,23], [mary,14], [hello]]
  • 一个含有三个元素的列表。三个元素中的每一个也是一个列表。
1
[1, john, ['199y', john]]
  • 另一个三元素列表。
1
[[]]
  • 一个一元素的列表。它所包含的唯一元素是一个空列表。

Elements and Lists

元素（element）”和“列表（list）”不是一回事

  • [anna] [\neq] anna
  • [[]] [\neq] []

Heads and Tails

Prolog 经常通过把列表分解为 头(head) + 尾(Tails) 来递归处理

非空列表（non-empty list）

在一个非空列表里：

  • Head（头）：列表的第一个元素
  • Tail（尾）：除了第一个元素以外的剩余部分

并且有一个非常重要的点：

Tail 一定还是一个列表
它等价于“原列表去掉 head 后剩下的列表”

空列表（empty list）

空列表 [] 没有 head，也没有 tail，因为里面什么都没有。

例子

对列表：[a, b, c, d]

  • Head = a
  • Tail = [b, c, d]

对列表：[anna]

  • Head = anna
  • Tail = []（空列表）

Try it yourself…

Identify the head and the tail of the following lists:

[parsley, sage, rosemary, thyme]

Head（头）：`parsley`
Tail（尾）：`[sage, rosemary, thyme]`
`[[a, b], c, d]`
Head（头）：[a, b]
Tail（尾）：[c, d]
`[[loneRanger]]`
Head（头）：[loneRanger]
Tail（尾）：[]

Lists as Prolog Terms

我们现在知道四种 Prolog 项：常量、变量、数字和列表。

在 Prolog 中有两种不同的写列表的方法：基本方式和带杠方式(barred way)。

到目前为止我们所看到的方式是基本方式

1
[1,-4, Z, [a, X, ‘b 2’], joe]

“barred way是一种不同的符号表示，用于将表头与表尾分开。这对于递归列表处理很有用。

列表的头部(head)先出现，然后是竖线|，接着是尾部(tail)。

Basic way: [1, X, 3]

1
Barred way: [1 | [X, 3]]

请注意，尾部(tail)是一个列表
因此在带杠（barred）的表示法中，尾部周围总是会多一对括号

Lists and Unification

列表和带变量的谓词()一样，可以进行“统一”（unify）

而且：基本写法的列表可以和带竖线写法的列表统一

  • 例子：
1
2
3
4
unify p([X, 3 | Z]) with p([b, Y, c, b])
X=b
Y=3
Z=[c, b]

  • [X] and [a]

    • X=a

  • [X,X] and [[Y,a,c],[b,a,c]]

    • Y=b, X=[b,a,c]

  • [a,b,c] and [a|[b,c]]

    • Same list in different notations

  • [X|Y] and [a]

    • X=a, Y=[]

  • [a,b,c] and [X|Y]

    • X=a, Y=[b,c]

Lists that Fail to Unify

情况 1：元素个数不同

情况 2：存在不匹配的元素

例子：

  • [a] and []
  • [] and [[]]
  • [X,Y] and [U,V,W]
  • [a,b,c] and [X,b,X]
  • [X|Y] and []

TRY IT YOURSELF

How do the following lists unify?

  1. [a,b,X] and [Y,b,Y]

    点击展开答案 Y = a
    X = a

  1. [[X]] and [Y]

    点击展开答案 Y = [X]

  1. [a,b,c] and [a|[b|[c]]]

    点击展开答案 true

  1. [a|[b,c]] and [a,X,Y]

    点击展开答案 X = b
    Y = c

  1. [X,Y|Y] and [a,[b,c],b,c]

    点击展开答案 X = a
    Y = [b,c]

Built-In List Functions

1
2
3
4
5
?-length([1,3,6],What).
What = 3

?-append([a],[b],NewList).
NewList = [a, b]

append被添加的项必须是列表——Prolog将其处理为在竖线符号的后面

结构角度理解 append

append([a],[b]) 本质就是：

1
[a | []]  +  [b | []]

变成：

1
[a | [b | []]]

就是

1
2

[a,b]
1
2
3
?-append(X,[1,2],[1,1,2]%求解X + [1,2] = [1,1,2]
X= [1]
false	%没有更多解了。

append(L1, L2, Result)意思是L1 + L2 = Result

1
2
?- reverse([1,2],ReversedVersion).
ReversedVersion = [2,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
?- member(a,[a,b,c]).
true

?- member(b,[a,b,c]).
true

?- member(c,[a,b,c]).
true

?-member(Element,[a,b,c]).
Element = a
Element = b
Element = c

? – member(Element,[a,[b,c]]).
Element = a
Element = [b, c]
1
2
3
4
?- member(Element,[a|[b,c]]).
Element = a
Element = b
Element = c

Recursive List Predicates 递归列表谓词

检查元素是否在list中

1
2
party([H|_]) :- friend(H).
party([_|T]) :- party(T).

递归tail列表,每次递归判断head是否是friend如果不是则继续递归直到找到friend= true 或到达list末尾

如何检查一个列表是否包含另一个列表的所有元素

1
2
3
4
5
6
containsAll(_,[]).
containsAll(List,[H|T]):- member(H, List),
containsAll(List,T).

?- containsAll([sam,bob,alex,findlay,bill],[sam,alex,findlay]).
true

用member判断头元素是否在list内

Practice Question

Can you test if all the items in a list are unique?

  • (Hint: Use member.)

  • unique([a,b,c]) should return true

    unique([a,b,b]) should return false

点击展开答案 unique([_]).
unique(H|T):- \+ member(H,T),unique(T).

Infinite Recursion

1
?- member(3, L).

会导致无限递归

1
2
3
4
5
6
7
8
member(X, [_|T]) :-
    member(X, T).
    
?- member(3,L).
L = [3|_G214] ;
L=[_G213，3|_G217];
L=[_G213，_G216，3|_G220];
...

无限增长

原因因为逻辑上：包含 3 的列表有无限多个

正确使用方式

1
?- member(3, [1,2,3]).
  • 有限
  • 正常
  • 会停止

5 - Constraint Satisfaction