3

我正在尝试深入研究以下 GNU Prolog 行为：

test(X,I,O) :- phrase(X,I,O).
?- test(("a",!,"b"),"ab","").

有没有标准的方法来查看短语/3 的翻译？

根据 ISO DCG 提案 (*)，我们需要有一个 expand_term/2。现在我可以用它来检查：

?- expand_term((foo --> "a", !, "b"),X).
X = (foo([97|A],B):-!,A=[98|B])

这是否告诉我在我的 test/3 中如何使用短语/3？

(*) ISO/IEC DTR 13211–3:2006
定句语法规则
Klaus Daessler
2012 年 11 月 20 日
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dcgs/dcgsdin121120.pdf

4

2 回答 2

3

有没有标准的方法来查看短语/3 的翻译？

没有。 的意思phrase/3是定义的，但是后面的实际实现是不可访问的。有几种不同的方式，如何phrase/3定义。它可以像在 YAP中一样简单：

phrase(P, S0, S) :-
        call(P, S0, S).

或者它可以使用expand_term/2（或类似的东西）。那是：

phrase(P, S0, S) :-
   expand_term(( pseudont --> P ), ( pseudont(CS0, CS) :- Goal) )),
   S0 = CS0,
   S = CS,
   Goal.

它可以在调用后执行最终的统一Goal：

phrase(P, S0, S) :-
   expand_term(( pseudont --> P ), ( pseudont(CS0, CS) :- Goal) )),
   S0 = CS0,
   Goal,
   S = CS.

并且通过引入（依赖于实现的）约定，扩展的谓词总是在最后一个参数中使用未实例化和未别名的变量调用，这将允许在存在半上下文的情况下进行尾递归。

这完全取决于实施者。

这是否告诉我在我的 test/3 中如何使用短语/3？

不，没有办法说。

但是，你为什么要问？或者，换个说法：

不同但一致的实现会phrase/3产生什么影响？

资源消耗

这应该是显而易见的。考虑?- phrase([],Xs).哪个不会在 YAP 中的堆上创建任何术语，但会为上面的 naive expand_term-expansion 这样做。但是，资源消耗超出了当前标准的范围。

变量排序

考虑..., phrase([], Xs, Xs), ...YAP 中规则的主体：Xs仍然是局部变量，而expand_term基于 - 的短语使其成为全局变量。在许多实现中，这会影响变量的相对顺序。现在，标准在 7.2.1 中明确指出：

如果 X 和 Y 是不相同的变量，则
X term_precedes Y 应依赖于实现
，除非在创建排序列表（
7.1.6.5、8.10.3.1 j）期间排序应保持不变。

所以这又不是问题，但这仍然可能很烦人。

NSTO财产

Prolog 标准（即第 1 部分 ISO/IEC 13211-1）仅在 NSTO 时定义执行。也就是说，如果在执行期间发生的所有统一都是 NSTO — 不受发生检查的影响（参见 7.3.3）。

现在，考虑您的情况：phrase(("a",!,"b"), Xs, Ys). 乍一看，这相当于phrase("ab", Xs, Ys). 但现在考虑假设set_prolog_flag(double_quotes,chars)

?- Xs = [c|_], Xs = Ys, phrase(("a",!,"b"), Xs, Ys).

毫无疑问，这个查询应该会失败。但它是 NSTO 吗？天真地，我们可以假设这可以替换为：

?- Xs = [c|_], Xs = Ys, Xs = [a,b|Ys].

这相当于：

?- Xs = [c|_], Xs = [a,b|Xs].

显然，Xs = [a,b|Xs]只有 STO （受发生检查）。而且两者一起都是STO！要理解这一点，请考虑 7.3.2 中的 Herbrand 算法。本质上，它“以任何顺序”不确定地重写方程。这是一个这样的推导：

          Xs = [c|Zs], Xs = [a,b|Xs].
(7.3.2 f) Xs = [c|Zs], [c|Zs] = [a,b,c|Zs].
(7.3.2 d) Xs = [c|Zs], c = a, Zs = [b,c|Zs].
(7.3.2 g) failure (not unifiable, positive occurs-check)

当然，这种推导是不寻常的。通常，在 存在的情况下会立即失败c = a，但该算法在这方面是不确定的。只有当所有可能的推导都不导致 7.3.2 g 时，一组方程才是 NSTO。引用 7.3.3：

一组方程（或两项）是“不受
发生检查”（NSTO）的，如果没有办法继续执行
Herbrand 算法的步骤，从而
发生 7.3.2 g。

冻结/2 和何时/2

这些构造也可能受到影响。尽管现有标准文件目前未涵盖它们，但了解潜在影响仍然具有相关性。考虑：

?- freeze(L, (X=1;X=2)), phrase(("a",!,"b"),L).
L = [a, b],
X = 1.

B、SICStus、SWI、YAP 都产生了这一答案。所以削减意义重大。

无论如何，感谢您的提问——我仅在回答您的问题时才理解 NSTO 问题！这显然对如何制定 DCG 翻译有一些影响。

于 2013-01-04T02:30:43.253 回答
1

由于 ISO DCG 没有定义一种方法来确定哪个短语/3 用作执行术语，因此唯一的方法是查阅源代码。在这里可以找到：

http://sourceforge.net/projects/gprolog/

短语/3 谓词在名为 expand.pl 的文件中定义。它的定义使用'$dcg_trans_body'/4。我们可以检查一下：

GNU Prolog 1.4.2
By Daniel Diaz
Copyright (C) 1999-2012 Daniel Diaz
| ?- '$dcg_trans_body'(("a",!,"b"), In, Out1, Body).

Body = (!,A=[98|Out1])
In = [97|A]

所以第一个终端确实合并到了 In 参数中，类似于 foo 规则。由于这是在调用 phrase/3 时完成的，所以这应该不是问题。

于 2013-01-04T03:51:47.497 回答