0

我遇到过这段代码：

connectRow(_,_,0).
connectRow([spot(_,R,_,_)|Spots],R,K) :- K1 is K-1, connectRow(Spots,R,K1).

/*c*/
connectRows([]).
connectRows(Spots) :- 
   connectRow(Spots,_,9),
   skip(Spots,9,Spots1), 
   connectRows(Spots1).

connectRow(Spots,_,9) 中的通配符如何工作？它如何知道要检查哪些值以及它如何知道它检查了所有可能的值？

编辑：我想我理解为什么会这样，但是如果有人可以为我验证这一点，我会很高兴：当我使用通配符“调用”connectRow 时，它会匹配带有 connectRow 谓词中的“R”的通配符。会是这样吗？

4

1 回答 1

2

_就像任何其他变量一样，除了您看到的每个变量都被视为不同的变量，Prolog 不会向您显示它与什么相结合。那里没有特殊行为；如果它使您对行为感到困惑，只需发明一个全新的变量并将其放入其中以查看其作用。

让我们谈谈Prolog如何处理变量。这是一个你可以遵循的实验，如果你碰巧有它们，它应该会破坏无益的先入为主的观念。

?- length([2,17,4], X)
X = 3.

很多 Prolog 看起来像这样，很容易陷入这样的陷阱，即认为有指定的“输出”变量像返回值一样工作，而指定的“输入”变量像参数一样工作。毕竟：

?- length([2,17,4], 3).
true.

?- length([2,17,4], 5).
false.

在这里，我们开始看到一些有趣的事情正在发生。错误的直觉是 Prolog 以某种方式跟踪输入和输出变量并在这种情况下“检查”。但这不是正在发生的事情，因为统一比这更普遍。观察：

?- length(X, 3).
X = [_G2184, _G2187, _G2190].

我们现在颠覆了传统的参数/返回值：Prolog 知道 X 是一个包含三个项目的列表，但不知道这些项目实际上是什么。信不信由你，当您知道需要多少变量但不需要单独命名时，这种技术经常用于生成变量。

?- length(X, Y).
X = [],
Y = 0 ;

X = [_G2196],
Y = 1 ;

X = [_G2196, _G2199],
Y = 2 ;

X = [_G2196, _G2199, _G2202],
Y = 3

碰巧长度的定义非常笼统，Prolog 可以使用它来生成列表及其长度。这种行为是 Prolog 如此擅长“生成和测试”解决方案的部分原因。你在逻辑上定义你的问题，Prolog 应该能够生成逻辑上合理的值来测试。

所有这些变化都源于一个非常简单的长度定义：

length([], 0).
length([_|Rest], N1) :-
  length(Rest, N0), 
  succ(N0, N1).

关键是不要把它看成一个计算长度的过程，而是把它看作是列表和数字之间的逻辑关系。该定义是归纳的，将空列表与 0 相关联，将包含一些项目的列表与 1 + 列表其余部分的长度相关联。进行这项工作的引擎称为统一。

在第一种情况下，length([2,17,4], X)值 [17,4] 与 Rest 统一，N0 与 2 统一，N1 与 3 统一。该过程是递归的。在最后一种情况下，X 与 [] 统一，Y 与 0 统一，这自然会导致下一种情况，即我们有一些项目并且 Y 为 1，并且表示列表中项目的变量没有任何内容的事实特别是统一并不重要，因为该变量的值从未使用过。

查看您的问题，我们看到了相同的递归结构。谓词非常复杂，所以让我们将它们分解。

connectRow(_, _, 0).

这说connectRow(X, Y, 0)的是真的，不管 X 和 Y。这是基本情况。

connectRow([spot(_, R, _, _)|Spots], R, K) :-

此规则匹配特定结构的点列表，假设第一个点的第二个值 (R) 与第二个参数匹配。

K1 is K-1, connectRow(Spots, R, K1).

该子句的主体本质上是在递减第三个参数 K 时重复出现的。

现在很清楚，这基本上会生成一个看起来像[spot(_, R, _, _), spot(_, R, _, _), ... spot(_, R, _, _)]长度 = K 的列表，并且在其他三个位置没有特定值spot。事实上，这就是我们在测试时看到的：

?- connectRow(X, Y, 0).
true ;
(infinite loop)^CAction (h for help) ? abort
% Execution Aborted

?- connectRow(X, Y, 2).
X = [spot(_G906, Y, _G908, _G909), spot(_G914, Y, _G916, _G917)|_G912] ;
(infinite loop)^CAction (h for help) ? abort

所以这里似乎有一些错误；如果我确定这些就是整个故事，我会说：

  • 基本情况应该使用空列表而不是匹配任何东西
  • 我们应该在归纳情况下规定 K > 0
  • clpfd如果我们希望能够产生所有可能性，我们应该使用

进行更改我们会得到稍微不同的行为：

:- use_module(library(clpfd)).

connectRow([], _, 0).
connectRow([spot(_, R, _, _)|Spots], R, K) :- 
  K #> 0, K1 #= K-1, connectRow(Spots, R, K1).

?- connectRow(X, Y, 0).
X = [] ;
false.

?- connectRow(X, Y, 1).
X = [spot(_G906, Y, _G908, _G909)] ;
false.

?- connectRow(X, Y, Z).
X = [],
Z = 0 ;

X = [spot(_G918, Y, _G920, _G921)],
Z = 1 ;

X = [spot(_G918, Y, _G920, _G921), spot(_G1218, Y, _G1220, _G1221)],
Z = 2

您会注意到，在结果中，我们的结构中有 Y spot，但我们在其他位置有看起来很奇怪的自动生成变量，例如_G918. 碰巧的是，我们可以使用_而不是 Y 并看到类似的效果：

?- connectRow(X, _, Z).
X = [],
Z = 0 ;

X = [spot(_G1269, _G1184, _G1271, _G1272)],
Z = 1 ;

X = [spot(_G1269, _G1184, _G1271, _G1272), spot(_G1561, _G1184, _G1563, _G1564)],
Z = 2

所有这些看起来很奇怪的变量都在那里，因为我们使用了_. 请注意，所有spot结构在第二个位置都有完全相同的生成变量，因为 Prolog 被告知它必须将 的第二个参数connectRow与 的第二个位置统一spot。这在任何地方都是正确的，因为 R 被递归地“传递”到下一个对 connectRow 的调用。

希望这有助于解释_您的示例中发生了什么，以及一般的 Prolog 统一。

编辑：用 R 统一一些东西

要在下面回答您的问题，您可以直接将 R 与一个值统一，或者将其绑定到一个变量并使用该变量。例如，我们可以直接绑定它：

?- connectRow(X, 'Hello, world!', 2).
X = [spot(_G275, 'Hello, world!', _G277, _G278), spot(_G289, 'Hello, world!', _G291, _G292)]

我们也可以绑定它，然后再分配它：

?- connectRow(X, R, 2), R='Neato'.
X = [spot(_G21, 'Neato', _G23, _G24), spot(_G29, 'Neato', _G31, _G32)],
R = 'Neato'

说起来没什么特别的R=<foo>；它统一了表达式的两边，但两边都可以是表达式而不是变量：

?- V = [2,3], [X,Y,Z] = [1|V].
V = [2, 3],
X = 1,
Y = 2,
Z = 3.

所以你也可以在另一个谓词中使用 R：

?- connectRow(X, R, 2), append([1,2], [3,4], R).
X = [spot(_G33, [1, 2, 3, 4], _G35, _G36), spot(_G41, [1, 2, 3, 4], _G43, _G44)],
R = [1, 2, 3, 4] ;

请注意，这为回溯和生成其他解决方案创造了机会。例如：

?- connectRow(X, R, 2), length(R, _).
X = [spot(_G22, [], _G24, _G25), spot(_G30, [], _G32, _G33)],
R = [] ;

X = [spot(_G22, [_G35], _G24, _G25), spot(_G30, [_G35], _G32, _G33)],
R = [_G35] ;

X = [spot(_G22, [_G35, _G38], _G24, _G25), spot(_G30, [_G35, _G38], _G32, _G33)],
R = [_G35, _G38] ;

希望这可以帮助！

于 2013-01-23T22:49:35.427 回答