Predicate member/2 - Reflections based on "The Craft of Prolog" by Richard O'Keefe

Discussion
1

Hello,
I received “The Craft of Prolog” a couple of days ago, and I started giving a look at chapter one yesterday. It’s really an interesting book, there are many observations that let the reader pay attention to the “little details”.
One of the things it starts with is the predicate member/2, which is one of the really basic ones, but even there there are some interesting observations to make.

  1. in most languages there is a clear and sharp distinction between inputs and outputs, what a function expects to receive and what it returns. In Prolog the distinction is not so clear, many predicates are bidirectional, so to say, and depending on what you want to do, you can use them either in a way or in another
  2. this holds true for the member/2 predicate as well. The predicate is defined by two clauses:
member(X, [X|_]).
member(X, [_|T]) :-
        member(X, T).

Two clauses: a base case and a recursive step. Either something is the head of a list (and then you’re done, that something is a member of the list), or it isn’t (and then you have to take a recursive step and see if you find it in the tail). Because one is dealing with a recursive data type (a list) all seems clear and no problematic at all. But actually this definition has some further implications:

As O’Keefe says, anything that matches the head of first clause, will also match the head of the second, this will create a choice point: even if an element is found in the list’s head that won’t mean that the predicate is finished with its job. If one is using it in an interactive environment, he’ll get a “true” as an answer, but the cursor will stay there blinking, waiting for a full stop or a semicolon. This is not what one would expect from a “normal” member function: as soon as you hit what you wanted to check, you exit the computation and return True. There’s nothing to wait for.
So you think: ok, I might use a cut (!) to prune the alternatives, and rewrite the first clause like this:

member(X, [X|_]) :- !.

this gives you a behavior which is more similar to what one would get in a more standard programming language, but this prevents from using member/2 to extract all values of the list.

If you submit a query with the first argument instantiated, then you’re using the predicate to check if a value is in the list:

member(a, [a, s, d])

(the funny thing is that if the value is found more than once in the list you’re searching, and you force backtracking by adding a semicolon, you’ll get “true” multiple times and you start thinking “ok, but this is counting, not checking whether something is a member of a list” (and you might think member is not exactly the right name for the predicate).

?- member(a, [a, s, d, a, f, a]).
true ;
true ;
true.

But you can submit a query with an uninstantiated variable, in that case the predicate will extract all values, if you force backtracking by hitting the semicolon:

?- member(X, [a, s, d, a, f, a]).
X = a ;
X = s ;
X = d ;
X = a ;
X = f ;
X = a.

Adding a cut in the first clause wouldn’t allow for this use of the predicate. So wouldn’t one want two distinct predicates maybe? A member with cut for the usual checking mechanism, and a backtrackable version to generate all values…

2

The cut doesn’t have to be in the library code, it could be in your calling code if you know the intention, e.g. member(X,Y),!,more stuff. For your example above, a separate predicate does exists memberchk/2, and a more modern idiom of only checking if a predicate succeeds at least once, is once/1.

2 Likes
3

I imagined that alternatives had already been worked at…but you know… for the sake of discussion…do you know if memberchk/2 is a Swi-Prolog idiom or common to other implementations?
Thanks

4

You should check a few more Prolog implementations. You could start at the Prolog wikipedia page and click your way from there.

1 Like
5

But this is a lot of work…I hoped you already knew… :sweat_smile: for the moment the distinction member/memberchk is enough. I will try out once/1 to understand how it works

7

I didn’t say that O’Keefe invented anything. He presents what I assume is the “classical” version of member/2 without any cuts. But the predicate does something clearly different from just checking whether something is member of a list. What does the Gertjan van Noord trick consist of? I don’t know the trick. If you don’t mind explaining it. In Variant 2 the original member/2 is simply encapsulated within the memberchk/2 call, if I get it right.

9

See the library version. It enhances on the classical implementation in two ways: it gets the head/tail of the list only once per iteration and it is deterministic when matching the last element of the list. So, it is faster and reduces choice points.

memberchk/2 is around as long as I do Prolog AFAIK. It is in the lists library of most Prolog systems. But, there is no standard for the Prolog library, so there is no guarantee.

But, member/2 is a relation that says that the 1st argument is an element of the second argument that is a list. So, in member(X, [a,b,c]) it acts as a generator, similar to “for X in [a,b,c]” in some languages. And, you can also do member(a, L) which will try to add a to the list L. For example

?- L = [A,B,C,D], member(a, L).
L = [a, B, C, D],
A = a ;
L = [A, a, C, D],
B = a ;
L = [A, B, a, D],
C = a ;
L = [A, B, C, a],
D = a.

The trick is to stop thinking in doing/testing/…, but read it as “after this member/2 goal, the first argument is a member of the list”.

2 Likes
10

Using member/2 to instantiate a variable. That’s also something you don’t easily get to think of :clap:t2:

11

I expanded on your idea…using member/2 in this way is really crazy, but it’s fun

 L =[_, _, _], member(a, L), member(d, L), member(s, L), !.
L = [a, d, s].
12

Using append/3 is even more fun. For example (although some of these leave choicepoints that library versions don’t):

member(X, List) :- append(_, [X|_], List).
nextto(X, Y, List) :- append(_, [X,Y|_], List).
last(X, List) :- append(_, [X], List).
select(X, List, Rest) :-
    append(Head, [X|Tail], List), 
    append(Head,Tail, Rest).

etc.

1 Like
13

I’m happy with the fun of member/2 used to instantiate variables for today (I don’t think I would have ever had the idea). Even pleasures may become pains, if one exceeds :sweat_smile:
I leave these further pleasures to the more experienced

15

I don’t know (if it was one of those questions that you make to get an answer and not one of those you make because you already know it…)

16

You anticipated a thing I wanted to ask…whether time is the predicate to use in order to benchmark predicates in Swi prolog. It seems it is. Thanks

17

Yes.
I don’t have the book handy, but I think it had an example like this (if not in the book, then likely somewhere in the old “Prolog Digest”):

p([a|Rest],  ...) :- ...
p([b|Rest],  ...) :- ...

changed to

p([X|Rest], ...) :- p(X, Rest,  ...).
p(a, Rest, ...) :- ...
p(b, Rest, ...) :- ...

and the “Gertjan van Noord trick” looks very similar to some of Richard O’Keefe’s code (I suspect that this kind of thing has been independently invented or discovered multiple times).

19

I’m at page 20 or something…some time might pass before I reach the topic (although the book is not meant to be read linearly except for the first chapter he says…)

21

So access to a knowledge-base of facts is always faster and more efficient than accessing the same facts held in a list? Or is this true only for first arguments? This would mean: one had better give up lists entirely as a unefficient data structure and use bare facts? If your problem allows of course…
Thanks

PS: what are Lips in the output of the time/1 predicate? Something “per second”?

22

If you have a lot of facts, don’t use a list but use a data structure such as red-black trees (library(rbtrees)), with O(log N) access. I’ve found this sufficient for 100,000 terms; and that has made it easy to write code with lots of parallelism (no updates to “global” facts), so in the end, it was faster on a machine with multiple cores. (Note that adding/removing facts from a “global” database could be slower than adding/removing from an RB-tree, although I haven’t benchmarked this)

1 Like
23

Hi, just curious,

I would like to arise, in the field of member/2 discussion, problem of code optimalization, introducing 3rd clause in the middle of member/2 clauses:

member(X, [X|_]).
member(X, [_, X|_]). // or with other mutations
member(X, [_,_|T]) :-
    member(X, T).

I have intuition it can be better optimised in this form, by tabling for example.

1 Like
24

I’m on my smartphone so i can’t really interact at the moment. I’ll give this a try. Thanks

1 Like
25

It probably would be less confusing for member to actually be called e.g. member_any or member_anywhere :grinning:

1 Like