What are some best practices for writing Prolog predicates so that it works in different ways the arguments are specified

Question

I am trying to implement some simple predicates, something like my_length or my_append.

It is considered easy for me if we knew beforehand that we wanted to find the length of a list, or we wanted to append two lists. (i.e. I know what is input, what is output).

In Prolog, it is possible to do thing in other ways. Like my_length(L, 3), or my_append(A,B,[1,2,3]).

Sometimes, my code works. Sometimes, it doesn't.

I find it quite difficult to make sure it works in all sort of different ways. Unless it is just a helper predicate for myself, you never really know what your users want to test it with. Sometimes the problem can even be ill defined, it is unclear what should my_length(L, 5) outputs, for example.

Are there any best practices for that?

For practical programming, I found it much easier to just ignore these other ways and focus on only a particular way of calling. That's how I get things done, I am just worried about the possibility that someone else call it in a different way.

Is there a way for me to make that restriction at the language level? Or should I?

In particular, I am trying to write my_length such that it works for

1. Specifying list, calculating length, and
2. Specifying length, give me back a list that has length unbounded slot.

my_length([], 0).
my_length([_|T], A) :- my_length(T, TA), A is TA + 1.

That works fine both ways, except it prompts for more answers when I ask the reverse question, and then we get a stack overflow. We also can't do arithmetic with the length argument since it could be unspecified.

This is just a specific case.

Answer 1

Before answering your question, let's clarify what 'not working' may mean. It may mean that you may get an answer, but that answer is incorrect, like N = 3 when N = 2 would be the correct answer. Or it may mean that you get no answer, like a loop, instead. In traditional programming languages both are seen as undesirable and there is no clear distinction between those. In both cases such a program would be considered incorrect. But Prolog is a bit different here. The reason is that we have real variables at runtime. So we may have a list with two identical elements, say [X,X] which describes all possible lists with two identical elements. That is, we are describing here infinitely many such lists. Sometimes, these infinities can be described compactly, and sometimes this is not possible.

So infinity and its less popular companion non-termination are lurking around in Prolog right from the very first little programs on. We have to deal with it up front. Think of

?- append(L,[a],L).
   loops.

Looping behavior may be observed by getting a resource error, or just by a never ending query. In this particular case, all current Prolog systems will produce a resource error which causes some of them to abort completely.

What could be worse? Plenty! Think of

?- append(L,[a],L).
   L = [], unexpected.

Mastery of non-termination is absolutely essential in Prolog. In your case, the failure-slice

my_length([], 0) :- false.
my_length([_|T], A) :- my_length(T, TA), false, A is TA + 1.

pinpoints you to the very problem. The second argument has no influence on termination whatsoever! That is, all queries with a known length will terminate as good or bad as the same queries with a variable for the length. And thus only the first argument influences termination. Thus only lists of known length (and terms like [a,b|non_list]) will terminate. We need to modify something in the visible part of the program. Otherwise the problem will persist.

Now to fix the problem, we have several options

Stay pure

In many situations, the best is to stick to the pure, monotonic subset of Prolog and thus simply add a corresponding goal in front.

In SICStus and Scryer say²:

:- use_module(library(clpz)).

my_length2([], 0).
my_length2([_|T], A) :- #A #>0, #A #= #TA+1, my_length2(T, TA).

?- asserta(clpz:monotonic).

So in this new version, the second argument now influences termination just as the first one. (There are more efficient ways to write this even in the pure, monotonic subset.)

Another way to improve termination may be coroutining, like freeze/2 or when/2. In this particular case this would be insufficient. But sometimes it can do wonders. The downside is that you may now get answers that are not solutions.

Again another way is to rule out certain problematic cases by means of instantiation errors. Prefer list_si/1 and iwhen/2 over manual tests.

Handle instantiations explicitly

The other way is extremely difficult, as it requires to handle all different kinds of instantiations separately. Avoid this, unless you want to delve into systems' programming. Many programmers think they can handle this, only to leave out a case or two. You have seen the efficient code for Scryer. Let's leave it at looking at it.

Conclusion

So why are these things so complex in Prolog? Well, these problems exist equally in traditional programming languages but due to their less expressive formalism, you need to write much more code (like implementing a Prolog interpreter) to encounter the same problems. Often (in particular in the context of Hoare logic) one distinguishes between partial and total correctness. And the problem behind is even more profound, since there are problems that are only semi-decidable. That is, where non-termination (or any other form of non-answer) is the only possible answer.

---

_{2 For SWI say instead}

?- use_module(library(clpfd)).
?- op(150, fx, #).             % SWI misses this operator
?- asserta(clpfd:monotonic).

Answer 2

Without the dangers which come with being a generator going off to infinity:

list_length_freeze(Lst, Len) :-
    freeze(Len, (integer(Len), Len @>= 0)),
    list_length_freeze_(Lst, 0, Len).
    
list_length_freeze_(Lst, Upto, Len) :-
    % Checks for determinism
    (   Lst == [] -> Upto = Len
    ;   Upto == Len -> Lst = []
    % Base case
    ;   Lst = [], Upto = Len
    ;   Lst = [_|T],
        inc_int_below_max(Upto, Len, Upto1),
        when(
            (nonvar(T) ; nonvar(Len)),
            list_length_freeze_(T, Upto1, Len)
        )
    ).

% Increment, keeping to maximum (if specified)
inc_int_below_max(I, Max, I1) :-
    I1 is I + 1,
    % Check against Max if specified
    (integer(Max) -> I1 @=< Max ; var(Max)).

Results in swi-prolog:

?- list_length_freeze(Lst, Len).
Lst = [],
Len = 0 ;
Lst = [_|_A],
freeze(Len, (integer(Len), Len@>=0)),
when((nonvar(_A);nonvar(Len)), list_length_freeze_(_A, 1, Len)).

?- list_length_freeze(Lst, Len), (Lst = [a] ; Lst = [a,b]).
Lst = [a],
Len = 1 ;
Lst = [a, b],
Len = 2.

?- list_length_freeze(Lst, Len), Len = 3.
Lst = [_, _, _],
Len = 3.

?- list_length_freeze(L, L).
false.

?- freeze(L, (K = 1 ; K = 2)), list_length_max_freeze(L, 0).
L = [],
K = 1 ;
L = [],
K = 2.

?- list_length_freeze(L, N), L = [a|N], N = 1.
false.

That last example is an improvement over swi-prolog's length:

?- length(L, N), L = [a|N].
ERROR: Stack limit (1.0Gb) exceeded

Another way to prevent going off to infinity, is to use coroutining to set a maximum list length:

list_length_max_freeze(Lst, Max) :-
    freeze(Max, (integer(Max), Max @>= 0)),
    list_length_max_freeze_(Lst, Max, 0).

list_length_max_freeze_(L, Max, Upto) :-
    nonvar(Max),
    !,
    (   Max @> Upto
    ->  (   var(L)
        ->  freeze(L, list_length_max_freeze_(L, Max, Upto))
        ;   (   L = []
            ->  true
            ;   L = [_|T],
                Upto1 is Upto + 1,
                list_length_max_freeze_(T, Max, Upto1)
            )
        )
    ;   Max == Upto
    ->  L = []
    ).
list_length_max_freeze_(L, Max, Upto) :-
    (   var(L)
    ->  when((nonvar(L) ; nonvar(Max)),
            list_length_max_freeze_(L, Max, Upto)
        )
    ;   (   L = []
        ->  freeze(Max, Max @>= Upto)
        ;   L = [_|T],
            Upto1 is Upto + 1,
            when((nonvar(T) ; nonvar(Max)),
                list_length_max_freeze_(T, Max, Upto1)
            )
        )
    ).

Results in swi-prolog:

?- list_length_max_freeze(Lst, 3).
freeze(Lst, list_length_max_freeze_(Lst, 3, 0)).

?- list_length_max_freeze(Lst, 3), length(Lst, 2).
Lst = [_, _].

?- list_length_max_freeze(Lst, 3), length(Lst, Len).
Lst = [],
Len = 0 ;
Lst = [_],
Len = 1 ;
Lst = [_, _],
Len = 2 ;
Lst = [_, _, _],
Len = 3.

Answer 3

Can use -> (implies) with == (compare without instantiation), for determinism:

list_length(Lst, Len) :-
    % Start at zero
    list_length_(Lst, 0, Len).

% Found end of list
list_length_(Lst, Upto, Len) :-
    % Checks for determinism
    (   Lst == [] -> Upto = Len
    ;   Upto == Len -> Lst = []
    % Base case
    ;   Lst = [], Upto = Len
    % Iterate through list
    ;   Lst = [_|T],
        inc_int_below_max(Upto, Len, Upto1),
        list_length_(T, Upto1, Len)
    ).

% Increment, keeping to maximum (if specified)
inc_int_below_max(I, Max, I1) :-
    I1 is I + 1,
    % Check against Max if specified
    (integer(Max) -> I1 @=< Max ; var(Max)).

Results in swi-prolog:

?- list_length([a,b,c], Len).
Len = 3.

?- list_length(Lst, 3).
Lst = [_, _, _].

?- Lst = [a,b,c], list_length(Lst, Len).
Len = 3.

?- Lst = [a,b|Tail], list_length(Lst, 1).
false.

?- freeze(L, (L = [a] ; L = [b])), list_length(L, 1), L = [b].
L = [b].

?- X = N, length([a,b|X], N).
false.

?- freeze(L, (K = 1 ; K = 2)), list_length(L, 0).
L = [],
K = 1 ;
L = [],
K = 2.

This avoids unwanted choicepoints.