prologsequenceterminationfailure-slicelogical-purity

How to implement list item deletion for all argument modes?

The following Prolog program defines a predicate deleted/3 for deleting all the occurrences of the item passed in first argument from the list passed in second argument and results in the list passed in third argument:

deleted(_, [], []).
deleted(X, [X|Y], Z) :-
  deleted(X, Y, Z).
deleted(U, [V|W], [V|X]) :-
  deleted(U, W, X),
  U \= V.
  1. It works with queries in this argument mode:
?- deleted(a, [a, b, a], [b]).
   true
;  false.
  1. It also works with queries in this argument mode:
?- deleted(X, [a, b, a], [b]).
   X = a
;  false.
  1. It also works with queries in this argument mode:
?- deleted(a, [a, b, a], Z).
   Z = [b]
;  false.
  1. It also works with queries in this argument mode:
?- deleted(X, [a, b, a], Z).
   X = a, Z = [b]
;  X = b, Z = [a, a]
;  false.
  1. It also works with queries in this argument mode:
?- deleted(a, Y, Z).
   Y = Z, Z = []
;  Y = [a], Z = []
;  Y = [a, a], Z = []
;  Y = [a, a, a], Z = []
;  Y = [a, a, a, a], Z = []
;  …
  1. It also works with queries in this argument mode:
?- deleted(X, Y, Z).
   Y = Z, Z = []
;  Y = [X], Z = []
;  Y = [X, X], Z = []
;  Y = [X, X, X], Z = []
;  Y = [X, X, X, X], Z = []
;  …
  1. But it exhausts resources with queries in this argument mode:
?- deleted(a, Y, [b]).
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb
  Stack depth: 1,225,203, last-call: 0%, Choice points: 1,225,183
  Possible non-terminating recursion:
    [1,225,203] deleted(a, _1542, [length:1])
    [1,225,202] deleted(a, [length:1|_1584], [length:1])
  1. It also exhausts resources with queries in this argument mode:
?- deleted(X, Y, [b]).
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb
  Stack depth: 1,225,179, last-call: 0%, Choice points: 1,225,159
  Possible non-terminating recursion:
    [1,225,179] deleted(_1562, _1564, [length:1])
    [1,225,178] deleted(_1596, [length:1|_1606], [length:1])

How to implement list item deletion for all argument modes?

Solution

  • Intro

    Pure Prolog conjunctions and disjunctions are, in fact, commutative and associative.

    This allows us to ignore clause and goal order, provided that all answer sequences are finite.

    When queries have infinite solution sets, Prolog may need to systematically enumerate infinite answer sequences.

    The fix

    To help Prolog find answers for above “problematic” queries, swap the two recursive rules:

    deleted(_,[],[]).
deleted(U,[V|W],[V|X]) :-  % this clause was last
   dif(U,V),
   deleted(U,W,X).
deleted(X,[X|Y],Z) :-
   deleted(X,Y,Z).

    Demo

    Let’s run your queries again with above code changes!

    The finite ones work like before1:

    ?- deleted(a,[a,b,a],[b]).         % Q1
   true
;  false.

?- deleted(X,[a,b,a],[b]).         % Q2
   X = a
;  false.

?- deleted(a,[a,b,a],Z).           % Q3
   Z = [b]
;  false.

?- deleted(X,[a,b,a],Z).           % Q4
   Z = [a,b,a], dif(X,a), dif(X,b)
;  Z = [a,  a],               X=b
;  Z = [  b  ],     X=a
;  false.

    Some infinite ones were okay before—they still are:

    ?- deleted(a,Y,Z).                 % Q5
   Y = Z, Z = []
;  Y = Z, Z = [_A],       dif(_A,a)
;  Y = Z, Z = [_A,_B],    dif(_A,a), dif(_B,a)
;  Y = Z, Z = [_A,_B,_C], dif(_A,a), dif(_B,a), dif(_C,a)
;  …

?- deleted(X,Y,Z).                 % Q6
   Y = Z, Z = []
;  Y = Z, Z = [_A],       dif(X,_A)
;  Y = Z, Z = [_A,_B],    dif(X,_A), dif(X,_B) 
;  Y = Z, Z = [_A,_B,_C], dif(X,_A), dif(X,_B), dif(X,_C)
;  …

    Some infinite ones used to be “problematic”—not anymore:

    ?- deleted(a,Y,[b]).               % Q7
   Y = [b]
;  Y = [b,a]
;  Y = [b,a,a]
;  Y = [b,a,a,a]
;  …

?- deleted(X,Y,[b]).               % Q8
   Y = [b],         dif(X,b)
;  Y = [b,X],       dif(X,b)
;  Y = [b,X,X],     dif(X,b)
;  Y = [b,X,X,X],   dif(X,b)
;  Y = [b,X,X,X,X], dif(X,b)
;  …

    Analysis

    Now, ?- deleted(X,Y,[b]). makes Prolog give us answers.

    But why did we run ? How come it did not work?

    To explain this, let’s take a step back: the default / vanilla / out-of-the-box of many2 Prolog systems initially runs each query until it discovers either (0) finite failure or (1) the 1st answer3.

    Before the fix, we observed neither. Why not?

    1. Why no finite failure?

      deleted(a,[a,b,a],[b]) holds true.

      Therefore, the more general deleted(X,Y,[b]) must not fail.

    2. Why no (1st) answer?

      Prolog proceeds depth-first, top-down, left-to-right.

      So when …

          ?- deleted(X,Y,[b]).

      … “meets” …

          deleted(X,[X|Y],Z) :-
       deleted(X,Y,Z).

      … inside the Prolog machine, the following happens:

      • A choicepoint is created for saving the information—to be used upon backtracking—that another clause could have been selected.

      • Next, Prolog proceeds with a recursive goal which is just like the original one: we are no closer to an answer, as the 3rd argument—the only instantiated one—stays exactly the same.

      Eventually, this loop runs out of memory—which is exactly the behavior that you observed.

    If we swap two recursive clauses, the following clause becomes our top-most recursive clause:

    deleted(U,[V|W],[V|X]) :-
   dif(U,V),
   deleted(U,W,X).

    Now, something is going on with the 3rd argument: Prolog recursively walks down the single-linked list until [] (or a free logical variable) is reached. Only then can Prolog make use of the fact deleted(_,[],[]). and give us an answer.

    Footnotes:

    1. In fact better, as we preserve by using dif/2 for expressing syntactic term inequality.

      More on dif/2:

    2. All based Prolog systems I have ever used.

    3. Not stopping at the 1st answer is way better for code quality—particularly in regard to universal termination properties.

      GUPU, an excellent environment specialized for Prolog and constraint programming courses, does the right thing—by default!

      “Answer substitutions are displayed in chunks of five.”