Why does this give a choicepoint?

Thanks to some great help in another thread, I have a basic understanding of choicepoints, but obviously still haven’t got it clear.

I was trying an exercise in a book, in which the aim was to write a predicate translate(Ints, Words) that succeed if Ints is a list of integers, and Words is a translation of those integers into the word equivalents, so translate([1,2], [one, two]) would succeed.

I did my first attempt before asking that other question, and ended up with the following code…

means(0, zero).
means(1, one).
means(2, two).
% other clauses for means() omitted for clarity
translate([N], [W]) :-
  means(N, W).
translate([H1,H2|T], Res) :-
  means(H1, W),
  translate([H2|T], Tt),
  append([W], Tt, Res).

This works, but gives a choicepoint.

Having watched the video that @brebs linked in that other question (several times), I can’t understand why this gives a choicepoint, as the first argument to the two clauses seem to be clearly distinct. The way I currently understand it, the first argument of the first clause would only match a list of exactly one element, whereas the first argument of the second clause would only match a list of at least two elements.

Can anyone explain why this code gives a choicepoint?

Since watching that video a few times, I was able to write a different version that didn’t give a choicepoint…

tr([], []).
tr([H|T], Res) :-
  means(H, W),
  tr(T, Tt),
  append([W], Tt, Res).

However, I’d still like to understand why my first version gives a choicepoint. Thanks for any help you can give.

I don’t think that this is an answer, but what I remember is that - when processing a list - you will always need (at least) two clauses: one dealing with the base-case, the other one dealing with the recursive step, so to say. And the base-case is when you reached the end of the list, that is the empty list. This might look like this

tr([], []).

in your code, or it might look like this

tr([], Last, Last).

if you’re passing a value using an accumulator or something of that kind. Actually I don’t understand why you’re trying to use a list with one element as the base-case instead of the empty list. But this wasn’t helpful possibly. Someone will provide a theoretically more solid answer

@anon419083 Thanks for the reply.

I didn’t bother with the case when the list was empty, as it’s not relevant. Once you get down to one element, you’ve hit the base case. You can’t translate an empty list.

As it happens, my second version of the code does use an empty list as the base case, and it could be that this is why it doesn’t generate a choicepoint, but I want to understand why my first version does, when I would have thought that argument indexing should have been able to avoid that.

Thanks again.

I remember vaguely that Prolog does not make a choice point for
two clauses predicate for lists like this.

a([], R):- ...
a([X|Y], R):- ...		

Before knowing that, I always put cut (!) after the head of the first clause
for not having the choice point.

Note that first argument indexing only looks at constants and functors. Both these clauses have the list functor. It would have to look at the second argument of the term to figure out the second clause won’t match after the first one did. It doesn’t look that far. Normally you’d use what is known as a green cut; a cut that doesn’t change the semantics. This is relatively tricky. These days, if you do not care about portability, i’d use

translate([N], R) =>
    R = [W],
    means(N, W).
translater([H1,H2|T], R) =>
    ...

See old discussions on SSU (Single Sided Unification)

As a follow-up to the discussion above, does this give a choice-point? I guess no, because the empty list is special,

means(0, zero).
means(1, one).
means(2, two).
% other clauses for means() omitted for clarity
translate([], []).
translate([H | T], [W | Res]) :-
  means(H, W),
  translate(T, Res).

I can :slight_smile:

Yes, with:

translate(X, Y).

The thing to avoid is what I like to call unwanted choicepoints, when we feel the program should be cleverer :grinning: - example.

Hee hee, got me there! I realised late last night that I had phrased that badly. What I meant was that my original line of thought was that the base case was a list of a single element, as there was nothing to do with an empty list.

As you can see from my second go at the problem, I did indeed account for translating an empty list :wink:

1 Like

Hmm, I think this is where my understanding of argument indexing was faulty. I was assuming that Prolog looked at the structure of a list, so could differentiate between [], [H] and [H1,H2|T] and so on.

Sounds like you’re saying that is can only differentiate between [] (which is sees as a constant), and any other list (which it sees as a functor).

Is that right? Thanks

The classic way of not having a choice point when the base case is a singleton list is to use an auxiliary predicate (note the order of arguments to translate_/3:

translate([H|Ns], Ws) :-
    translate_(Ns, H, Ws).

translate_([], N, [W]) :-
    means(N, W).
translate_([H2|T], H1, Res) :-
    means(H1, W),
    translate([H2|T], Tt),
    append([W], Tt, Res).

And the call to append/3 isn’t needed; you can instead do this:

translate([H|Ns], Ws) :-
    translate_(Ns, H, Ws).

translate_([], N, [W]) :-
    means(N, W).
translate_([H2|T], H1, [W|Tt]) :-
    means(H1, W),
    translate([H2|T], Tt).

And this situation is so common, that there’s a meta-predicate maplist/3:

translate(Ns, Ws) :-
    maplist(means, Ns, Ws).

and if an empty list is supposed to fail:

translate(Ns, Ws) :-
    Ns = [_|_],
    maplist(means, Ns, Ws).

yes. Although, if it has a many clauses say [1|], [2|], etc. it will look at the first argument of each list. These refinements are currently examined if there are more than 10 candidate clauses.

ok, got it…

?- translate(X, Y).
X = Y, Y = [] ;
X = [0],
Y = [zero] ;
X = [0, 0],
Y = [zero, zero] ;

and so on. Technically correct though

@jan Thanks for clarifying that.

I didn’t understand what you meant by “it will look at the first argument of each list” though, please can you clarify.

Thanks again

@peter.ludemann Thanks for that, very useful tips there.

As it happens, whilst browsing some of the links in this thread (and links from them, etc) I came across a video on meta predicates. I’m still digesting it, but I can see how they can make your code cleaner.

@Yossu In the term [foo,bar], foo is the first argument of the list. It's also the first (and only) argument of [foo]`.

If you want to see what’s going on, you can use jiti_list (e.g., jiti_list(user:means/2). I tried this with

p([1], [one]).
p([2], [two]).
p([3], [three]).
p([4], [four]).

and it showed “indexed” as 1. When I increased the number of clauses to 14, it showed “indexed” as 1/1, which showed that it was indexing deeper into the term.

(If you just consult the facts, jiti_list won’t show anything – you need to trigger the “just-in-time indexing” by calling the predicate.)

Ho hum, thought I’d got it, but obviously haven’t :disappointed_relieved:

I’m now trying to write my own version of [subset/2[(SWI-Prolog -- subset/2), which is true if all elements of the first list belong to the second list, but have hit a choicepoint.

My code is (called it subst to avoid a clash with the built-in predicate)…

subst([], _).
subst([H|T], S) :-
  member(H, S),
  subst(T, S).

Now, given that the first clause has a constant (empty list) as its first argument, and the second clause has a list functor as its first argument, why does this give a choicepoint? If I try subst([1], [1,2,3]). it comes up with true, then waits for me to press ; at which point it comes up with false.

Why the choicepoint, and why does it come up with false the second time?

Sorry to ask so many basic questions, but I’d really like to understand this. Thanks again.

member/2 gives all results on backtracking, e.g.

?- member(X, [1,2,3]).
X = 1 ;
X = 2 ;
X = 3.
?- member(1, [1,2,3,1]).
true ;
true.

Notice how it succeeds twice in the second example.

If you want only the first result, use memberchk/2.

You code will do:

?- subst(X,[1,2,3]).
X = [] ;
X = [1] ;
X = [1,1] ;
X = [1,1,1] ;
X = [1,1,1,1] ;
X = [1,1,1,1,1] ;
X = [1,1,1,1,1,1] ;
X = [1,1,1,1,1,1,1] ;
X = [1,1,1,1,1,1,1,1] ;
   ...

@peter.ludemann Thanks as always for your excellent explanation. Not come across jiti_list before, one to play with!

Thanks for pointing that out, not what I expected, but makes sense when you point it out.

If member/2 isn’t doing exactly what’s wanted, for a particular circumstance, then it’s easy to write a variation.

Example: If the list is known to be unique, and choicepoints are undesired:

member_unique(E, [H|T]) :-
    (   member_unique_(T, H, E)
    ->  true
    ;   member(E, [H|T])
    ).

member_unique_(_, H, E) :-
    H == E,
    % No more than 1 match in list
    !.
member_unique_([H|T], _P, E) :-
    member_unique_(T, H, E).

Comparative results:

?- E = 2, member_unique(E, [1, 2, 3]).
E = 2.  % No undesired choicepoint
?- E = 2, member(E, [1, 2, 3]).
E = 2 ;
false.  % Undesired choicepoint, comparing to 3

There’s a performance impact here, of course. Just showing options :grinning: