在Prolog中实现经常出现的决定论模式

Question

在Prolog中编程时,我经常编写谓词,当所有参数被实例化时,其行为应该是半确定性的(否则其行为应该是非确定性的).

一个具体的用例就是我的谓词walk/3,它实现了图形遍历.由于两个顶点之间可以存在多条路径,因此实例化后(+,+)会给出多个选择点true.然而,这些都是无用的.once/1出于性能原因,必须明确使用调用代码.

%! walk(+Graph:ugraph, +StartVertex, +EndVertex) is semidet.
%! walk(+Graph:ugraph, -StartVertex, +EndVertex) is nondet.
%! walk(+Graph:ugraph, +StartVertex, -EndVertex) is nondet.
%! walk(+Graph:ugraph, -StartVertex, -EndVertex) is nondet.

半决定论可以通过once/1在调用上下文中使用来强制,但我想将半决定论作为谓词的属性来实现walk/3,而不是每次被调用时都需要特别对待的东西.

除了对代码美学的关注之外,调用上下文不必总是知道它的调用是否walk/3是半确定性的.例如:

%! cycle(+Graph:ugraph, +Vertex) is semidet.
%! cycle(+Graph:ugraph, -Vertex) is nondet.

cycle(Graph, Vertex):-
  walk(Graph, Vertex, Vertex).

我提出了以下解决方案,它确实产生了正确的行为.

walk_wrapper(Graph, Start, End):-
  call_ground_as_semidet(walk(Graph, Start, End)).

:- meta_predicate(call_ground_as_semidet(0)).
call_ground_as_semidet(Goal):-
  ground(Goal), !,
  Goal, !.
call_ground_as_semidet(Goal):-
  Goal.

但是,这种解决方案存在不足之处:

• 它不够通用,例如有时候ground应该是nonvar.
• 它不具有风格,每次使用时都需要额外的谓词包装.
• 它也可能效率稍低.

我的问题是:有没有其他方法可以在Prolog中对通常出现的(非)确定性模式(如此处描述的模式)进行一般/高效/风格编程？

Answer 1

你应该尝试将双重否定视为失败。是的，基本目标只能是真或假，所以它不应该留下任何选择点。为了让事情变得简单，假设我们有一个非循环图：

如果我使用这段代码：

edge(a, b).         edge(a, c).
edge(a, d).         edge(b, c).
edge(c, d).         edge(c, e).
edge(d, e).

path(X,X).
path(X,Y) :- edge(X,Z), path(Z,Y).

Prolog 系统现在将为封闭查询留下选择点：

?- path(a, e).
true ;
true ;
true ;
true ;
true ;
false.

在我看来，为了消除这些选择点并拥有多模式谓词，推荐的方法是在 Prolog 中使用所谓的元编程。

元编程有时也被贬义地称为非逻辑编程，因为它基于非逻辑谓词，例如 ground/1、!/0 或 (+)/1。但是，当声明性不受影响时，我们可以将其称为元编程。

您可以按如下方式编写包装器 smart/1，与 call_ground_as_semidet/1 执行相同的操作，但有一些细微差别：

smart(G) :- ground(G), !, \+ \+ G.
smart(G) :- G.

Prolog 系统将不再为封闭查询留下选择点：

?- smart(path(a,e)).
true.

\+ \+ 相对于 Once 的优点在于，前者不仅不留下任何选择点，而且还删除了踪迹。它有时被称为Prolog 的垃圾收集元谓词。