# Question about select/3?

**URL:** <https://swi-prolog.discourse.group/t/question-about-select-3/856>\
**Category:** Help!\
**Created:** [June 24, 2019, 1:49am UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856 "2019-06-24T01:49:00Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![prodog](https://avatars.discourse-cdn.com/v4/letter/p/57b2e6/32.png) [@prodog](https://swi-prolog.discourse.group/u/prodog)\
**Post date:** [June 24, 2019, 1:49am UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/1 "2019-06-24T01:49:00Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [June 24, 2019, 2:09am UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/2 "2019-06-24T02:09:34Z")

</div>

> [@prodog](#):
>
> What does “… the last element of List1 has been selected” mean

```prolog
?- 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:

```prolog
?- select(X, [a], Z).
X = a,
Z = [].

```

---

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [June 24, 2019, 9:48am UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/3 "2019-06-24T09:48:16Z")

</div>

Just to add even more context to Peter’s answer. In a textbook, you might find a `select/3` definition that looks like this:

```prolog
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:

```prolog
?- 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](https://www.swi-prolog.org/pldoc/doc/_SWI_/library/lists.pl?show=src#select/3) 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](https://www.swi-prolog.org/pldoc/man?section=jitindex); 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.

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [June 24, 2019, 3:44pm UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/5 "2019-06-24T15:44:19Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [June 24, 2019, 7:11pm UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/6 "2019-06-24T19:11:34Z")

</div>

> [@jan](#):
>
> why does this single choice point matter enough to write this implementation rather than the textbook one, one may ask?

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](https://www.swi-prolog.org/pldoc/man?section=jitindex)

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [June 24, 2019, 7:24pm UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/7 "2019-06-24T19:24:27Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [June 24, 2019, 11:43pm UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/8 "2019-06-24T23:43:08Z")

</div>

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)

```prolog
select(Head, [Head|Rest], Rest).
select(Select, [Head|Rest1], [Head|Rest2]) :-
    select(Select, Rest1, Rest2).

```

gives

```prolog
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)`:

```prolog
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

```prolog
pred([X|Xs], ...) :- 
    pred1(X), 
    pred2([X|Xs], ...).

```

… does it get transformed to something like this (with “deep” indexing)

```prolog
pred([Arg1, ...) :- 
    Arg1=[X|Xs], 
    pred1(X), 
    pred2(Arg1, ...).

```

(I see this pattern fairly often in some of my code).

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [June 25, 2019, 6:57am UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/9 "2019-06-25T06:57:33Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [June 26, 2019, 1:04am UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/10 "2019-06-26T01:04:03Z")

</div>

> [@jan](#):
>
> ZIP way for passing arguments

Example please? (I’m not familiar with this jargon)

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [June 26, 2019, 12:09pm UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/11 "2019-06-26T12:09:58Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![swi](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@swi](https://swi-prolog.discourse.group/u/swi)\
**Post date:** [June 26, 2019, 3:04pm UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/12 "2019-06-26T15:04:18Z")

</div>

So how could this be re-written using the “Zip way” in  
order to take advantage of argument indexing (without recreating the cell again)?

> [@peter.ludemann](#):
>
> ```prolog
> pred(Arg1, ...) :- 
> Arg1=[X|Xs], 
> pred1(X), 
> pred2(Arg1, ...).
> 
> ```

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [June 26, 2019, 3:57pm UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/13 "2019-06-26T15:57:40Z")

</div>

> [@swi](#):
>
> how could this be re-written

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 🙂

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [June 26, 2019, 4:14pm UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/14 "2019-06-26T16:14:15Z")

</div>

I’m still curious what “Zip way” means (always eager to learn new tricks).

---

<div class="post-metadata">

**Author:** ![michaelby](https://avatars.discourse-cdn.com/v4/letter/m/b3f665/32.png) [@michaelby](https://swi-prolog.discourse.group/u/michaelby)\
**Post date:** [June 26, 2019, 5:34pm UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/15 "2019-06-26T17:34:12Z")

</div>

ZIP is the virtual machine design SWI-Prolog is based on - a simpler variant of the WAM, I believe. Maybe Jan has a reference.

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [June 26, 2019, 6:00pm UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/16 "2019-06-26T18:00:40Z")

</div>

(I had forgotten that the VM was called “ZIP”).

I think these are the references:

[Bowen, Kenneth A.; Buettner, Kevin A.; Cicekli, Ilyas; and Turk, Andrew, “The Design and Implementation of a High-Speed Incremental Portable Prolog Compiler” (1985)](https://surface.syr.edu/cgi/viewcontent.cgi?article=1009&context=eecs_techreports)

[Bowen, Byrd, Clocksin: A portable Prolog compiler (1983)](https://www.researchgate.net/publication/273888197_A_portable_Prolog_compiler)

---

<div class="post-metadata">

**Author:** ![michaelby](https://avatars.discourse-cdn.com/v4/letter/m/b3f665/32.png) [@michaelby](https://swi-prolog.discourse.group/u/michaelby)\
**Post date:** [June 27, 2019, 6:10am UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/17 "2019-06-27T06:10:56Z")

</div>

> [@peter.ludemann](#):
>
> I think these are the references:

Thanks for these!

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [June 27, 2019, 8:20am UTC](https://swi-prolog.discourse.group/t/question-about-select-3/856/18 "2019-06-27T08:20:32Z")

</div>

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](http://www.swi-prolog.org/download/publications/A_Portable_Prolog_Compiler.pdf). Since then, a lot has changed. Still, one can recognise some parts of the design in the current code base.