prolog - 查看 phrase/3 翻译的标准方法？

Question

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

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

有没有标准的方法来查看 phrase/3 翻译了什么？

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

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

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

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

Answer 1

Is there a standard way to see the what phrase/3 translates?

没有。定义了phrase/3的含义，但后面的实际实现是不可访问的。 phrase/3 有几种不同的定义方式。它可以像 in 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.

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

这完全取决于实现者。

Does this tell me how phrase/3 is used in my test/3?

没有，没有办法说。

但是，你为什么要问？或者，换句话说:

What effect could a differing but conforming implementation of phrase/3 have?

资源消耗

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

变量排序

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

If X and Y are variables which are not identical then
X term_precedes Y shall be implementation dependent
except that during the creation of a sorted list (7.1.6.5,
8.10.3.1 j) the ordering shall remain constant.

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

NSTO 属性

Prolog 标准(即 ISO/IEC 13211-1 第 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:

A set of equations (or two terms) is "not subject to
occurs-check" (NSTO) iff there exists no way to proceed
through the steps of the Herbrand Algorithm such that
7.3.2 g happens.

freeze/2 和 when/2

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

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

B、SICStus、SWI、YAP 都产生了这个答案。所以削减很重要。

---

无论如何，感谢您的提问——我只是在回答您的问题时才了解 NSTO 问题!这显然对 DCG 翻译的制定方式产生了一些影响。