Should I enforce mode declarations by throwing instantiation errors?

Question

I have been working on some code in which I have predicates that either do not terminate or give incorrect solutions if they are used in certain modes.

Here is an example:

%!  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
...

So my question is, am I better off throwing an error if the first argument is not instantiated?

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).

I have been reading through some Prolog libraries such as apply.pl, which on my system is located in /usr/local/logic/lib/swipl/library/apply.pl. Here is code directly from this library. Note that no instantiation errors are mentioned anywhere here.

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

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

Yet if I use this predicate like so I get an instantiation error:

?- 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.

I do not understand how Prolog knows to throw this error.

I would. Use `must_be/2` and for the types missing you can add types using `has_type/2`. If you need more details ask at the [SWI-Prolog forum](https://swi-prolog.discourse.group/), for which I see you are already a member. — Guy Coder, Nov 09 '20 at 23:43
I believe the `maplist` error comes from the special handling of `call`, which requires its goal argument to be instantiated and callable. — Isabelle Newbie, Nov 10 '20 at 00:32

false · Answer 1 · 2020-11-11T16:18:44.130

4

am I better off throwing an error if the first argument is not instantiated?

In your case not much. In fact, the non-termination you encountered was annoying and resource-wasting but at least not incorrect. I would be more concerned about cases like:

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

It gets even worse in the presence of constraints.

As a general rule-of-thumb, whenever you want to discern according to instantiations, test for the more instantiated pattern. In your case, do not test with var/1, instead rather use nonvar/1. This focuses your attention on the safer case. And in your case you might have realized that nonvar/1 alone is not enough. In fact, use ground/1:

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

Consider using iwhen/2 to hide the details; and get an easy upgrade to coroutining: just delete the i and you are using when/2.

In general, instantiation errors are here to mask out procedural problems. Some of them are related to non-termination, and others help to mask-out the non-relational parts of impure code like memberchk/2.

The question then remains, why write impure code in the first place? Even more so if it is quite inefficient as yours? With library(reif) you get a clean, pure and quite efficient solution:

:- 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).

Answering @gusbro's remark on performance in SWI, here is the expansion in SICStus Prolog (to get that listing, I declared list_nub/2 dynamic). The expansion should look similar in 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).

edited Nov 11 '20 at 16:18

answered Nov 10 '20 at 19:29

false

10,264
13
101
209

for large ground lists i get quite better timings with `list_without_duplicates` w.r.t. `list_nub`. – gusbro Nov 10 '20 at 20:55
@gusbro: `listing(list_nub)` to check if expansion is OK – false Nov 10 '20 at 22:36
I see `if_/3` being expanded. I tried to run it on swish but module `reif` seems to be missing there. [Here's the notebook](https://swish.swi-prolog.org/p/ist_nub%20vs%20list_without_duplicates.swinb), try it with `test1(10000, L)` and `test2(10000, L)`. On my local copy of SWI `list_nub/2` is two times slower. – gusbro Nov 11 '20 at 17:42
@gusbro: `memberchk/2` is a handwritten built-in. About twice as fast as the otherwise equivalent `once(member(X,Xs))`. – false Nov 11 '20 at 20:28
And: in your notebook, you use a `memberchk/2` only once. Without leaving any redundant choicepoints around. That's the version you compared `list_nub/2` to? – false Nov 11 '20 at 20:34
i checked both versions (the one without choicepoints and the one with them) and get better timings compared with `list_nub` (~60secs for list_nub, ~20secs for tweaked OPs version and ~25secs for OPs version+8secs to bail after asking more solutions). Don't get me wrong, I get that list_nub has better properties. But your statement about OPs version being inefficient and the pure one being efficient does not stand the empirical test. Both versions have basically the same algorithm underneath, keeping everything pure does seem to have some impact on performance. – gusbro Nov 11 '20 at 21:16
Apart from purity, leaving choicepoints open is a serious performance issue that cannot be measured in runtime. To complete your comparison, you should use `once(member(X,Xs))` since you rely here on an ad hoc optimization of `memberchk/2`. It seems reasonable that performance ratios will be comparable to [another](https://arxiv.org/abs/1607.01590) measurement. – false Nov 11 '20 at 23:18
1

Well I ran again the tests using `once(member(X,Xs))` instead of `memberchk(X,Xs)` and I now get comparable running times ~60secs for both OP algorithm and `list_nub`. Still getting 25% faster results when using `->/3` with `member/2` compared against `list_nub`. – gusbro Nov 12 '20 at 01:08
I am reassured :-). – false Nov 12 '20 at 19:01

TA_intern · Accepted Answer · 2020-11-10T12:27:56.427

I would refrain from directly throwing in your Prolog code unless you are absolutely certain you have no other choice.

Use the built-ins, they provide a lot of "type-checking" for free. Using call with a non-callable is one example. Basically all built-ins check their arguments and if they don't, I would consider this a bug and report it. Examples:

?- 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).

To rephrase, as long as you find the appropriate built-in to use in your own code, you shouldn't need to throw explicitly.

If you are checking the arguments, go ahead and use library(error).

The "without duplicates" predicate is a perennial classic. You need a very good reason to not use sort/2 for this. If you did use sort/2, you will immediately get an error:

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

If you decide to program it yourself, you might as well go down the rabbit hole and use if_/3 as suggested by @false. As a matter of fact, you might find a fancy solution here on SO if you simply look through the links in the profile of @false.

Should I enforce mode declarations by throwing instantiation errors?

2 Answers2