4

我一直在研究一些代码，其中我的谓词在某些模式下使用时不会终止或给出不正确的解决方案。

这是一个例子：

%!  list_without_duplicates(+List1, -List2) is det.
%
%   True if List2 contains all the elements of List1 but has
%   no duplicate elements. 
%
%   Ex: list_without_duplicates([1,1,2,2,3,3],[1,2,3]).

list_without_duplicates([],[]).
list_without_duplicates([X|Xs],[X|Acc]) :-
    \+ memberchk(X,Xs),
    list_without_duplicates(Xs,Acc).
list_without_duplicates([X|Xs],Acc) :-
    memberchk(X,Xs),
    list_without_duplicates(Xs,Acc).

% This is great.
?- list_without_duplicates([1,1,2,2,3,3],X).
X = [1, 2, 3] ; 
false.

% This is not great.
list_without_duplicates_(X,[1,2,3]).
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 1Kb, global: 0.8Gb, trail: 0.1Mb
ERROR:   Stack depth: 16,586, last-call: 100%, Choice points: 5
...

所以我的问题是，如果第一个参数没有实例化，我是否最好抛出错误？

list_without_duplicates(List1,List2) :-
    (  var(List1) 
    -> instantiation_error(List1)
    ;  list_without_duplicates_star(List1,List2)
    ).

list_without_duplicates_star([],[]).
list_without_duplicates_star([X|Xs],[X|Acc]) :-
    \+ memberchk(X,Xs),
    list_without_duplicates_star(Xs,Acc).
list_without_duplicates_star([X|Xs],Acc) :-
    memberchk(X,Xs),
    list_without_duplicates_star(Xs,Acc).

我一直在阅读一些 Prolog 库，例如apply.pl，在我的系统上位于/usr/local/logic/lib/swipl/library/apply.pl. 这是直接来自这个库的代码。请注意，此处没有提到任何实例化错误。

maplist(Goal, List1, List2) :-
    maplist_(List1, List2, Goal).

maplist_([], [], _).
maplist_([Elem1|Tail1], [Elem2|Tail2], Goal) :-
    call(Goal, Elem1, Elem2),
    maplist_(Tail1, Tail2, Goal).

然而，如果我像这样使用这个谓词，我会得到一个实例化错误：

?- use_module(library(apply)).
true.

?- apply:maplist(X,[1,2,3],[4,5,6]).
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:   [11] apply:maplist_([1,2|...],[4,5|...],apply:_5706)
ERROR:    [9] toplevel_call(user:apply: ...) at /usr/local/logic/lib/swipl/boot/toplevel.pl:1113
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.

我不明白 Prolog 是如何知道抛出这个错误的。

4

2 回答 2

4

如果第一个参数没有实例化，我最好抛出错误吗？

在你的情况下不多。事实上，您遇到的不终止是烦人且浪费资源的，但至少不是不正确的。我会更关心以下情况：

?- Y = b, list_without_duplicates([a,Y],[a,b]). 
   Y = b
;  false.                         % inefficiency                         
?-        list_without_duplicates([a,Y],[a,b]).
   false.                         % incompleteness

在存在约束的情况下，情况会变得更糟。

作为一般经验法则，每当您想根据实例进行识别时，请测试更多实例化的模式。在您的情况下，不要使用 进行测试var/1，而是使用nonvar/1. 这会将您的注意力集中在更安全的情况上。在您的情况下，您可能已经意识到nonvar/1仅此而已是不够的。事实上，使用ground/1：

list_without_duplicates(List1,List2) :-
    (  ground(List1) 
    -> list_without_duplicates_star(List1,List2)
    ; instantiation_error(List1)
    ).

考虑使用iwhen/2隐藏细节；并轻松升级到协程：只需删除i您正在使用的when/2.

通常，实例化错误是为了掩盖程序问题。其中一些与非终止有关，而另一些则有助于屏蔽不纯代码的非关系部分，例如memberchk/2.

那么问题仍然存在，为什么首先要编写不纯的代码？如果它和你的效率一样低，更是如此？与library(reif)您一起获得干净、纯净且相当高效的解决方案：

:- use_module(library(reif)).
list_nub([], []).
list_nub([X|Xs], Ys0) :-
   if_(memberd_t(X,Xs), Ys0 = Ys1, Ys0 = [X|Ys1]),
   list_nub(Xs, Ys1).

回答@gusbro 关于 SWI 性能的评论，这里是 SICStus Prolog 中的扩展（为了获得该列表，我声明为list_nub/2动态）。SWI 中的扩展应该看起来相似。

list_nub([], []).
list_nub([A|B], C) :-
        memberd_t(A, B, D),
        (   D==true ->
            C=E
        ;   D==false ->
            C=[A|E]
        ;   nonvar(D) ->
            throw(error(type_error(boolean,D),type_error(call(user:memberd_t(A,B),D),2,boolean,D)))
        ;   throw(error(instantiation_error,instantiation_error(call(user:memberd_t(A,B),D),2)))
        ),
        list_nub(B, E).
于 2020-11-10T19:29:46.360 回答
3

除非您绝对确定您别无选择，否则我会避免直接输入您的 Prolog 代码。

使用内置插件，它们免费提供大量“类型检查”。与不可调用对象一起使用call就是一个例子。基本上所有内置程序都会检查他们的参数，如果他们不这样做，我会认为这是一个错误并报告它。例子：

?- between(1, 3, foo).
?- succ(X, 0).
?- X = [_|X], length(X, N).
?- X is 3 - a.
?- X is 3 - A.
?- sort([a,b|c], Sorted).

换句话说，只要您找到合适的内置函数在您自己的代码中使用，您就不需要显式地抛出。

如果您正在检查参数，请继续使用library(error)。

“无重复”谓词是永恒的经典。你需要一个很好的理由不为此使用 sort/2 。如果你确实使用了 sort/2，你会立即得到一个错误：

?- sort(X, Y).
ERROR: Arguments are not sufficiently instantiated

如果您决定自己编程，您不妨钻进兔子洞并按照@falseif_/3的建议使用。事实上，如果您只需查看@false 配置文件中的链接，您可能会在 SO 上找到一个奇特的解决方案。

于 2020-11-10T07:31:09.250 回答