此代码的含义和作用是什么？

Question

我是Prolog新手，看不懂这段代码。你会怎么读这4个条款？他们在做什么？

a([]). 
a([_|L]):-b(L).

b([_]).
b([_|L]):-a(L).

谢谢。

Answer 1

参数模式很重要：

a) 列表显然是计数器，因为我们从不考虑内容。

b) 只是一个建议：将逻辑读作 productions，或读作 DCG

a-->[];[_],b.
b-->[_];[_],a.

待调用-例如

?- phrase(a, [w,h,a,t]).

Answer 2

正如@repeat 在他的评论中所建议的那样，运行一个一般的查询，这就是你得到的结果：

| ?- a(Xs).

Xs = [] ? ;

Xs = [_,_] ? ;

Xs = [_,_] ? ;

Xs = [_,_,_,_] ? ;

Xs = [_,_,_,_] ? ;

Xs = [_,_,_,_,_,_] ? ;

Xs = [_,_,_,_,_,_] ? ;
...

并且：

| ?- b(Xs).

Xs = [_] ? ;

Xs = [_] ? ;

Xs = [_,_,_] ? ;

Xs = [_,_,_] ? ;

Xs = [_,_,_,_,_] ? ;

Xs = [_,_,_,_,_] ? ;

Xs = [_,_,_,_,_,_,_] ? ;

Xs = [_,_,_,_,_,_,_] ? ;
...

所以如果Xs是一个包含偶数个元素的列表，a(Xs)成功，如果Xs是一个包含奇数个参数的列表，b(Xs)成功.如您所见，a/1 和 b/1 在每种情况下都成功了两次，除了 a([]). 只成功了一次。所以它不是确定列表长度奇偶校验的有效谓词。

让我们用更具描述性的名称重写这些：

even([]).
even([_|L]) :- odd(L).
odd([_]).
odd([_|L]) :- even(L).

现在让我们"read"他们怎么说：

[]是偶数列表
[_|L] 是偶数列表，如果 L 是奇数列表
[_] 是奇数列表
[_|L] 是奇数列表，如果 L 是偶数列表

这些听起来合乎逻辑，但为什么even/1和odd/1除了even([])之外两次都成功了？如果您查看 odd/1 的定义，[_] 有两种方法可以成功。一种是通过 odd([_]). 子句。第二个是第二个 odd/1，因为你会：

odd([_|[]]) :- even([]).  % [_] == [_|[]]

由于 even/1 和 odd/1 调用（even([]). 除外）最终会递归到对 odd([_]) 的调用，您将得到两个解决方案。

消除逻辑中歧义的一种方法是稍微重构它们。考虑以下递归规则：

一个至少包含 2 个元素的列表具有偶数个元素，前提是列表的尾部在前 2 个元素之后也是偶数。
如果列表的尾部在前 2 个元素之后也是奇数，则至少包含 2 个元素的列表的元素数为奇数。

将这些规则转化为 Prolog，包括之前的基本情况：

even([]).
even([_,_|L]) :- even(L).
odd([_]).
odd([_,_|L]) :- odd(L).

现在结果将是：

| ?- even(Xs).

Xs = [] ? ;

Xs = [_,_] ? ;

Xs = [_,_,_,_] ? ;

Xs = [_,_,_,_,_,_] ? ;
...

和

| ?- odd(Xs).

Xs = [_] ? ;

Xs = [_,_,_] ? ;

Xs = [_,_,_,_,_] ? ;
...

按照CapelliC的建议使用DCG，可以写出类似的规则：

even --> [] | [_,_], even.
odd --> [_] | [_,_], odd.

结果：

| ?- phrase(even, L).

L = [] ? ;

L = [_,_] ? ;

L = [_,_,_,_] ? ;
...

和

| ?- phrase(odd, L).

L = [_] ? ;

L = [_,_,_] ? ;

L = [_,_,_,_,_] ? ;
...

按照@false 的建议，对原始代码更直接的 "fix" 将消除 odd([_]). 的冗余基本情况，因为它已经被 even([]). 的基本情况所涵盖这也是比上面的解决方案简单一点，因为它利用了 even/1 和 odd/1 谓词之间的相互依赖性（在上面的解决方案中，even/1 和 odd/1 独立存在）。

even([]).
even([_|L]) :- odd(L).
odd([_|L]) :- even(L).

或者，在 DCG 中：

even --> [] | [_], odd.
odd --> [_], even.

此代码的含义和作用是什么？

What does this code mean and do?

list

prolog