Confused about choice points

Help!
1

Sorry if this is a dumb question, but I’m confused.

Whilst trying to work out why my code required me to press ; before I ended, even though there was only one solution, I came across the concept of choice points. Whilst I think I understand the idea, I can’t get my head around how it actually works.

For example, someone asked about this on SO, and whilst the answer there shows another way of writing the predicate to avoid choice points, it didn’t explain why there was a choice point in the first place.

The original code (which removed the last element from the list in the first argument) was…

list_withoutlast([_Last], []).
list_withoutlast([First, Second|List], [First|WithoutLast]) :-
  list_withoutlast([Second|List], WithoutLast).

If you try list_withoutlast([1], Res). then you get the result (Res = []), but then hit a choice point. Pressing * for more info gives…

% list_withoutlast([1],[]) left a choice point in alternate clause (after success)
%   c:/users/me/documents/prolog/choicepoints.pl:1: clause succeeded
%   c:/users/me/documents/prolog/choicepoints.pl:2: next candidate clause
% Called from
%    [9] toplevel_call(user:user: ...) at c:/program files/swipl/boot/toplevel.pl:1173

I really don’t understand this. That second predicate has a head whose first argument accepts a list with at least two elements, plus a (possibly empty) tail. How can Prolog think that this is a potential match when the list it’s handling only has one element?

Thanks for any help you can give.

2 Likes
2

First-argument indexing on lists is [] (empty list) vs [Head|Tail] (non-empty list). On the first argument only.

Which is not [Head] vs [Head1,Head2|Tail]

Video explanation and howto: Argument Indexing in Prolog - YouTube

1 Like
3

You can also define list_without_last:

list_without_last(List, WithoutLast) :- append(WithoutLast, [_], List).

This also leaves a choicepoint.

It’s possible to rewrite this so that there’s no choicepoint. I leave that as an exercise for you. :slight_smile:
As a hint, look at the source for last/2 (in library(lists)), which can be defined as
last(List, Last) :- append(_, [Last], List).

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).
2 Likes
4

@brebs Thanks for that, the video was excellent (as all of his are).

I realise now that as an imperative programmer (by day at least), I had an implicit assumption that “first argument” meant everything between the opening bracket and the first comma, so in the case of p([H|T],R). I thought of [H|T] as the first argument.

If I got it right, then only H is the first argument, which explains why there were choicepoints in the code I saw.

Thanks again.

5

@peter.ludemann Thanks for the reply. Having watched the video that @brebs linked, I can now understand your answer. I think that without it, I would still have struggled to understand why there was a choicepoint.

Thanks again

6

This is a nice quiz :+1:

7

Clause indexing is not specified in any standard AFAIK. Classical Prolog systems use the first argument and for compound terms only the name+arity. Many current systems do more, but how much is something you find only in the documentation and every system does its own thing. Bottom line though, systems use some sort of indexing to quickly find candidate clauses and if this detects there are no more candidates the call is deterministic. Else it creates a choicepoint. You can be fairly sure that this works for [] and [_|_], different atoms as first argument and a bit more.

1 Like