2

假设我有一个序言程序来连接这样的列表：

concat([],X,X).
concat([Head|Tail],X,[Head|R]) :- concat(Tail,X,R).

我怎么知道哪些问题会返回有限数量的答案？例如，询问

concat(X,Y,[1,2,3,4]).

将返回有限解集：

X = [],
Y = [1, 2, 3, 4] ;
X = [1],
Y = [2, 3, 4] ;
X = [1, 2],
Y = [3, 4] ;
X = [1, 2, 3],
Y = [4] ;
X = [1, 2, 3, 4],
Y = [] ;
false.

在提出问题的同时

concat(X,[2,3],Z).

将返回一组无限的解决方案：

X = [],
Z = [1, 2, 3] ;
X = [_G24],
Z = [_G24, 1, 2, 3] ;
X = [_G24, _G30],
Z = [_G24, _G30, 1, 2, 3] ;
X = [_G24, _G30, _G36],
Z = [_G24, _G30, _G36, 1, 2, 3] ;
X = [_G24, _G30, _G36, _G42],
Z = [_G24, _G30, _G36, _G42, 1, 2, 3] ;
X = [_G24, _G30, _G36, _G42, _G48],
Z = [_G24, _G30, _G36, _G42, _G48, 1, 2, 3] ;
X = [_G24, _G30, _G36, _G42, _G48, _G54],
Z = [_G24, _G30, _G36, _G42, _G48, _G54, 1, 2, 3]

依此类推（基本上，每个可能的列表都以 [1,2,3] 结尾。

那么我如何推断逻辑程序上哪些问题会结束呢？

4

3 回答 3

6

你在问如何确定一个逻辑程序的终止和非终止属性——这里指的是一个纯粹的、单调的 Prolog 程序。有一个好消息：是的，有很多技术可以找出这些属性以及很多有用的概念。

但在详细介绍之前，请记住，您的问题无法针对所有查询进行回答。也就是说，有些查询我们无法比实际执行查询更好地确认终止。但是不要让你被诸如不确定性之类的可怕词吓倒。他们来这里是为了回避焦虑。就像 旧的海图显示像红海蛇这样的可怕怪物。毫无疑问，海上存在问题：天气、营养不良、航海、叛乱、海盗、瘟疫、死水、冰山、地雷……你能说出它的名字。不过，遇到海怪的风险是可控的。

如今，我们拥有自己的海怪，它们使许多聪明的头脑无法解决有趣的问题。终止的不确定性过去几十年来一直如此。在过去的二十年里，情况变得更好了。所以：不要害怕！

首先要考虑的是您的逻辑程序打算描述的实际关系。你甚至不需要一个具体的程序来回答这个问题。想象一下这种关系。首先，问有多少解决方案。如果数量有限，那么这部分就完成了，因为没有内在的原因您的程序无法终止。（在您的示例中，一般关系包含无限多的解决方案：只要看到第三个参数中列表的长度无限多就足够了。）

如果有无限多，请尝试找到有限的查询子集。（在您的示例中，如果第三个参数是接地的，则只有有限多个解决方案。同上，如果第一个参数和第二个参数是接地的。但是，请注意，如果只有第一个参数是接地的，情况并非如此！）

另一个正交方向是考虑解决方案如何在 Prolog 中表示为答案。一些无限的解集可以用有限多个答案紧凑地表示。在约束的情况下，这变得特别有趣。（在您的示例中，考虑连接[]and [X]。在这里，第三个参数有无限多的解决方案，但它们都由单个答案替换表示A3 = [X]。）

有了上述考虑，我们对逻辑程序的期望有了一个粗略的估计：如果查询的解决方案集只能由无限的答案集表示，则程序不能终止。但是，如果解决方案可以由有限多个答案表示，则具体程序可能会终止。唉，为了保证程序确实终止，我们需要进一步挖掘并查看实际程序。

如果您现在查看您的程序，您可能会发现与预期关系有些不同。在您的示例中，查询concat([],[],[])失败，但它应该成功。但也concat([],nonlist,L)成功了。前者绝对是一个错字，后者是一种概括，通常被认为是可以接受的。

要了解具体查询的终止属性，请考虑目标Query, false。通过这种方式，您可以专注于相关属性、id est、终止并忽略不相关的属性，例如找到的具体解决方案。

您现在可以参考具体程序来确定程序的终止属性。考虑cTI，它确实推断程序的终止和非终止属性。以这种方式，可以确定推断的属性是否是最优的。

另一种方法是使用故障切片来确定程序的非终止片段。有关更多信息，请参阅类似的答案。

于 2013-10-01T17:46:31.710 回答
2

我通常使用这些规则：

  1. 每个新谓词必须使用不同的参数方向/类型进行测试。在您的情况下，方向是 (+, +, -), (+, -, +), (-, +, +), (-, -, +), (-, +, -), (+, - , -), (-, -, -)。“-”表示未绑定的变量，+ - 已经绑定了一些成员的变量。如果在同一位置带有“-”的情况有效，则“+”的情况将始终有效。因此，实际上您只能执行 4 次测试。我认为任何谓词都不会在 (-, -, ...) 模式下工作。只需从解释器命令行进行测试，您还不需要编写单元测试。

  2. 如果您发现某些结果不合适，请重新设计您的谓词。例如

    con_fin([],X,X).
con_fin(A,X,[Head|R]) :- nonvar(A), A=[Head|Tail], con_fin(Tail,X,R).

    将始终返回一组有限的答案。如果你还不能一口气写出完美的两行谓词（完美的谓词是有效地适用于所有可能方向的谓词）为不同的模式/类型写几行，让类型检查，如 var、nonvar、、X = [_|_]is_set /1 等成为你的朋友。

  3. 在那次测试之后做出明确的评论。您应该始终提及参数的可能类型和方向，并将谓词定义为某些模式的 det、semidet 或 nondet。我认为您的问题不是“（-，+，-）nondet”情况的无限解决方案，而是没有警告用户可能存在无限递归。

    B=[1, 2], con(A, B, C), A=[0].

    只需与以下案例进行比较

    B=[1,2], con(A, B, C), proper_length(C, 4), !.

    无效但正确和确定。

  4. 添加模式和类型检查。使用不当抛出异常。ISO 标准为某些情况（http://www.deransart.fr/prolog/exceptions.html）预定义了例外，良好的设计应遵循其建议。

  5. 编写一个涵盖所有可能用法的单元测试（通常不会超过 15 分钟，但您将来会节省更多）。

  6. 享受你的生活

  7. 如果您找到了更好的解决方案（Eureka！），只需重写谓词，现在单元测试就是您最好的朋友。

通常，Prolog 允许编写非常紧凑和智能的代码，但与其他语言相比需要更多的工作。可以像俳句一样在几年内改进一条小线。但是该语言的实际本质是try->test->use->redesign原则，因为在Prolog中进行实验非常容易。

于 2013-10-01T22:04:21.230 回答
0

您的程序 concat 并不完全正确，它应该是：

concat([],X,X).
concat([Head|Tail],X,[Head|R]) :- concat(Tail,X,R).

注意第二行的|in [Head|R]。您无法分析它是否会像@DanielLyons 所说的那样停止。您可以做的是使用“！”修剪解决方案树。

于 2013-10-01T16:01:19.317 回答