I’m using: SWI-Prolog version 8.0.2.
This doc page on select/3 say:
https://www.swi-prolog.org/pldoc/doc_for?object=select/3
Is true when List1, with Elem removed, results in List2. This implementation is determinsitic if the last element of List1 has been selected.
What does “… the last element of List1 has been selected” mean? I’m not sure what “selected” means in this context.
?- select(X, [1,2,3], Z).
X = 1,
Z = [2, 3] ;
X = 2,
Z = [1, 3] ;
X = 3,
Z = [1, 2].
The last result (X = 3, Z = [1, 2]) doesn’t have a “;” after it because there no more results – that is, it’s deterministic.
This query is also deterministic:
?- select(X, [a], Z).
X = a,
Z = [].
Just to add even more context to Peter’s answer. In a textbook, you might find a select/3 definition that looks like this:
select(X, [X|Xs], Xs).
select(X, [Y|Ys], [Y|Zs]) :- select(X, Ys, Zs).
(This would be “The Art of Prolog (Second Edition)” on page 67, Program 3.19)
With this definition, and Peter’s example:
?- select(X, [1,2,3], Z).
X = 1,
Z = [2, 3] ;
X = 2,
Z = [1, 3] ;
X = 3,
Z = [1, 2] ;
false.
Now we see the additional “;” and false. that you don’t see with the select/3 from library(lists). If you look at the implementation you will see the helper predicate. It puts the list in the first argument so that you get the [] vs [_|_] in the first argument, as discussed in the first bullet point here; to do this, it unpacks the second argument into head and tail (which is why the helper predicate has an extra argument).
PS: “selected” just means that it is now unified with the first argument, and is not in the list in the last argument.
And, why does this single choice point matter enough to write this implementation rather than the textbook one, one may ask? There appear to be quite a few cases where lists are produced that have in most cases only a single element, but they must be lists as multiple elements can happen. Using these enhanced member/2 and select/3 over such lists can reduce the number of open choice points significantly.
That is a minor problem in failure driven processing, but piling choice points in forwards recursion stops last call optimization and can drastically increase memory usage and decrease performance, mainly due to frequent and inefficient garbage collection (GC time mostly correlates with reachable memory with a small additional factor correlating with unreachable memory).
I thought that SWI-Prolog wasn’t restricted to indexing on the first argument, so why is this special code for member/2 or select/3 still needed?
Or did I misunderstand “indexing over multiple arguments” in SWI-Prolog -- Just-in-time clause indexing
The essential transformation is not about indexing, but to split the head and tail once per iteration and thus compare the remainder to [] or [_|_]. And yes, SWI-Prolog indexes on a lot of stuff such as other arguments, multiple arguments and inside compounds, but the rules that decide on these things are geared towards predicates with many clauses. Fixing this part would be part of what we discussed as dealing with a fairly low number of clauses.
Does SWI-Prolog do any simple transformations to remove duplicate patterns? For example, a simple mechanical transformation of Boris’ code for select/3 (with different variable names)
select(Head, [Head|Rest], Rest).
select(Select, [Head|Rest1], [Head|Rest2]) :-
select(Select, Rest1, Rest2).
gives
select(Select, [Head|Rest1], Rest2) :-
select2(Select, Head, Rest1, Rest2).
select2(Head, Head, Rest, Rest).
select2(Select, Head, Rest1, [Head|Rest2]) :-
select(Select, Rest1, Rest2).
which probably ends up generating one or two more virtual machine instructions than the code in library(lists):
select(X, [Head|Tail], Rest) :-
select3_(Tail, Head, X, Rest).
select3_(Tail, Head, Head, Tail).
select3_([Head2|Tail], Head, X, [Head|Rest]) :-
select3_(Tail, Head2, X, Rest).
The transformation in library(lists) for member/2 merely flips the arguments, presumably from the time when only first argument indexing happened.
And I’m curious what happens with something like
pred([X|Xs], ...) :-
pred1(X),
pred2([X|Xs], ...).
… does it get transformed to something like this (with “deep” indexing)
pred([Arg1, ...) :-
Arg1=[X|Xs],
pred1(X),
pred2(Arg1, ...).
(I see this pattern fairly often in some of my code).
As is, SWI-Prolog does no source code transformation except for eliminating some high order predicates if library(apply_macros) is loaded.
The last step you mention, dealing with common sub terms is not done either. Indexing does not look further than the head and thus such a transformation causes the clause not to be indexed.
For this particular case and the ZIP way for passing arguments we could probably add something to the compiler that would simply pass on the argument if a term that is equivalent to an argument term is used in the body.
Example please? (I’m not familiar with this jargon)
The VM passes arguments through the stack as an array of terms. So, if you find a term in the body that is (==) equivalent to one these arguments you could simply use the equivalent argument instead of recreating the equivalent term.
So how could this be re-written using the “Zip way” in
order to take advantage of argument indexing (without recreating the cell again)?
No way. Either the clause indexing must be extended to examine the body or the VM must be extended as I hinted. Pull requests will we seriously considered 
I’m still curious what “Zip way” means (always eager to learn new tricks).
ZIP is the virtual machine design SWI-Prolog is based on - a simpler variant of the WAM, I believe. Maybe Jan has a reference.
(I had forgotten that the VM was called “ZIP”).
I think these are the references:
Thanks for these!
The Bowen, Byrd and Clocksin paper is what started SWI-Prolog. It is really hard to find, but Steve Moyle found a copy for me, which I put on the SWI-Prolog website. Since then, a lot has changed. Still, one can recognise some parts of the design in the current code base.