Prolog append with cut operator

by

It sometimes really makes sense to introduce green cuts — even into append/3, but care must be taken that such a cut remains a green cut. That is, a cut that does improve efficiency (on a certain level) and does not affect answers.

There is a very simple rule-of-thumb for introducing green cuts: If you add a cut into a pure, monotonic program without any guard, you can be pretty sure that it will be a red cut which destructs the meaning of your program.

There are very few exceptions to this rule-of-thumb. For example, you may add a cut after a variable free goal, provided there is no further rule etc. It is definitely a good training to try to figure out cases that are affected by a cut.

But back to your program append2/3. Currently, the cut always cuts, even if the alternate rule does apply, in which case the cut removes answers which is what we want to avoid.

So when will the first clause be the only one of relevance?

If the first argument is [], thus append2([], Xs, Ys). – but also if the last argument is [] (there are even more cases which are more complex). Lets try both cases with the original cut-free definition:

?- append([], Ys, Zs).
   Ys = Zs.

?- append(Xs, Ys, []).
   Xs = Ys, Ys = []
;  false.

So in the first case, the system was able to determine that there is a single solution immediately, while producing the answer. In the second case, however, the Prolog system was not sure whether or not another answer will be necessary — it “left a choicepoint open” so to speak. This is a pity, since it is fairly trivial to determine that also in this case, only a single answer exists. A cut would have been ideal here to help. But an unguarded cut does more harm than it helps.

The cut may cut, provided the third argument is a []:

append3(Xs, Ys, Zs) :-
   (  Zs == [] -> ! ; true ),
   Xs = [],
   Ys = Zs.
append3([X|Xs], Ys, [X|Zs]) :-
   append3(Xs, Ys, Zs).

This program is now more efficient in the sense that it does not leave a choicepoint open, if only the 3rd argument is known.

?- append(Xs,Ys,[1]).
   Xs = [], Ys = [1]
;  Xs = [1], Ys = []
;  false.

?- append3(Xs,Ys,[1]).
   Xs = [], Ys = [1]
;  Xs = [1], Ys = [].

The program is not necessarily faster, since the test itself might be expensive. Ideally, a Prolog system would be able to do such things internally, but sometimes the programmer has to help a bit.

More Related Contents:

  1. Knowing when to use cut in prolog
  2. Prolog map procedure that applies predicate to list elements
  3. What is the difference between ‘ and ” in Prolog?
  4. Definition of a path/trail/walk
  5. Definition of Reflexive Transitive Closure
  6. Delete vowels in a list
  7. Reification of term equality/inequality
  8. Prolog successor notation yields incomplete result and infinite loop
  9. Finding Unique Items in a List
  10. Prolog: a person is a sibling of himself?
  11. What is the logical ‘not’ in Prolog?
  12. Using a constrained variable with `length/2`
  13. Einsteins Riddle Prolog
  14. Safer type tests in Prolog
  15. Complexity of ISO Prolog predicates
  16. Explanation of a Prolog algorithm to append two lists together
  17. list of the values in the leaf nodes of binary tree T
  18. Meaning of instantiation mode indicators in arguments of Prolog predicates
  19. Shuffle in prolog
  20. Collect all “minimum” solutions from a predicate
  21. Using \==/2 or dif/2
  22. Converting Terms to Atoms preserving variable names in YAP prolog
  23. Good beginners material on Prolog [closed]
  24. ‘if’ in prolog?
  25. Should I avoid tail recursion in Prolog and in general?
  26. Understanding Difference Lists
  27. Define graph in Prolog: edge and path, finding if there is a path between two vertices
  28. PROLOG: Determining if elements in list are equal if order does not matter
  29. Features of good Prolog code? [closed]
  30. GNU Prolog assert error

Leave a Comment