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

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…

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.

1 Like

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

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

1 Like

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

I guess it was not invented by Richard O Keefe, since his book is
from 1990, but I find it also in a 1988 book. But there are at least
two ways to implement it, namely:

Variant 1:

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

Variant 2:

memberchk(X, Y) :- member(X, Y), !.

I guess the second variant evolved, because one wants the backtracking
member/2 to implement the Gertjan van Noord trick, and then
reimplementing memberchk/2 with the Gertjan van Noord gets too

tedious, I even don’t know how it would look like, so falling back to
cutting member/2 is possibly feasible. Also maybe I am totally astray
that memberchk/2 would even need the Gertjan van Noord trick.

Then there are some further doubts about variant 2, a clever Prolog
system would realize variant 1 more efficiently I guess, using so
called “neck cut”, avoiding the creating of a choice point as

would happen in variant 2. SWI-Prolog has recently added some
native support to memberchk/2. So we have this variant 3. Not
sure when it made it into SWI-Prolog. Interesting find BTW:

Variant 3:

memberchk(E, List) :-
    '$memberchk'(E, List, Tail),
    (   nonvar(Tail)
    ->  true
    ;   Tail = [_|_],
	memberchk(E, Tail)
    ).

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.

memberchk/2 isn’t mentioned in Richard O’Keefes book.
There is a fourth way to defined memberchk/2:

Variant 4:

memberchk(X,Y) :- once(member(X,Y)).

Which is actually my favorite one. I am using it manually to “inline”
memberchk/2 in that I write the once/1+member/2 combo. Which
runs somehow in line with this proposal which doesn’t feature

deterministic memberchk/2, only the non-deterministic member/2

A Prologue for Prolog (working draft)
Ulrich Neumerkel, 2023-06-26 post-N290
https://www.complang.tuwien.ac.at/ulrich/iso-prolog/prologue

But who knows, maybe you wake up one day, and it has memberchk/2,
selectchk/3, etc… as well? But it looks rather that the author of the proposal
has a new and different fetisch, namely a built-in countall/2.

1 Like

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

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

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].

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

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

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…)

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

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).

Well the book has a topic register, which tells me:

indexing, 99, 297, 299-300

In the first part 99 he explains some interaction between
indexing and the cut. And in the second part 297, 299-300
he laments some indexing problems with DCG, similar to

what you showed. But he also laments 'C'/3, which you don’t
have in your example.

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…)

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”?

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