Q about findall/[3-4]: does it duplicate terms?

[Julio Di Egidio]

Hello guys, a question if you won't mind:

I am trying to collect terms with findall but I am losing the bindings.

Does findall/[3-4] duplicate terms before collecting?

Example:

?- L0 = [X, y(Y), z], findall(E, member(E, L0), L).
L0 = [X, y(Y), z],
L = [_G2443, y(_G2438), z].

If so, is there any other built-in I could use, or is coding a custom predicate the only way to keep bindings?

Thank you,

Julio

[Jan Wielemaker]

On 09/15/2016 09:15 AM, Julio Di Egidio wrote:
> Hello guys, a question if you won't mind:
>
> I am trying to collect terms with findall but I am losing the bindings.
>
> Does findall/[3-4] duplicate terms before collecting?

Yes. There isn't much else it can do. In *theory* it could share
terms that predate the findall call and are not instantiated by it.
Finding that a term predates a call isn't too hard (it is just further
down the stack), but figuring out whether or not it has been instantiated
will be rather hard (=slow). Without that, copying is the only option.
bagof/3
also copies all variables from the goal with each copy
of the template and restores these. That has its own problems.

Cheers --- Jan

> Example:
>
> |
> ?-L0 =[X,y(Y),z],findall(E,member(E,L0),L).
> L0 =[X,y(Y),z],
> L =[_G2443,y(_G2438),z].

> |
>
> If so, is there any other built-in I could use, or is coding a custom
> predicate the only way to keep bindings?
>
> Thank you,
>
> Julio
>

> --
> You received this message because you are subscribed to the Google
> Groups "SWI-Prolog" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to swi-prolog+...@googlegroups.com
> <mailto:swi-prolog+...@googlegroups.com>.
> Visit this group at https://groups.google.com/group/swi-prolog.
> For more options, visit https://groups.google.com/d/optout.

[Carlo Capelli]

Hi Julio

I think you can use bagof/3 instead of findall/3.
I found the behaviour by chance, after debugging some lost bindings while (ab)using findall/3 and constraints.

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.

To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.

[Julio Di Egidio]

On Thursday, September 15, 2016 at 9:26:27 AM UTC+2, Jan Wielemaker wrote:

On 09/15/2016 09:15 AM, Julio Di Egidio wrote:
> Hello guys, a question if you won't mind:
>
> I am trying to collect terms with findall but I am losing the bindings.
>
> Does findall/[3-4] duplicate terms before collecting?

Yes.  There isn't much else it can do.  In *theory* it could share
terms that predate the findall call and are not instantiated by it.
Finding that a term predates a call isn't too hard (it is just further
down the stack), but figuring out whether or not it has been instantiated
will be rather hard (=slow).  Without that, copying is the only option.

I have had look into pl-bag.c, but the code itself does not make clear why that

must be the case, i.e. why findall cannot just keep generated terms as they are.

Any way you can explain it, I mean unless it requires writing a little treatise?  :)

In any case, thank you both, Jan and Carlo, for your answers.

Julio

[Jan Wielemaker]

On 15/09/16 10:20, Julio Di Egidio wrote:
> On Thursday, September 15, 2016 at 9:26:27 AM UTC+2, Jan Wielemaker
> wrote:
>
> On 09/15/2016 09:15 AM, Julio Di Egidio wrote:
>> Hello guys, a question if you won't mind:
>>
>> I am trying to collect terms with findall but I am losing the
> bindings.
>>
>> Does findall/[3-4] duplicate terms before collecting?
>
> Yes. There isn't much else it can do. In *theory* it could share
> terms that predate the findall call and are not instantiated by it.
> Finding that a term predates a call isn't too hard (it is just
> further down the stack), but figuring out whether or not it has been
> instantiated will be rather hard (=slow). Without that, copying is
> the only option.
>
>
> I have had look into pl-bag.c, but the code itself does not make
> clear why that must be the case, i.e. why findall cannot just keep
> generated terms as they are. Any way you can explain it, I mean
> unless it requires writing a little treatise? :)

It is fairly easy: after the goal generates a solution, the system
backtracks for the next solution. Any term created while running
the goal is thus destroyed. If the term is older than the findall
goal this is of course not true, but any instantiation done by the
goal will be lost.

In general, variations of findall(X, member(X, List), XL) is not a
very good idea. You typically can get the same results using
library(apply) and library(yall) without copying anything. That
is often faster and at least as important it avoids all semantic
issues around copying (and saves memory).

Cheers --- Jan

>
> In any case, thank you both, Jan and Carlo, for your answers.
>
> Julio
>
> bagof/3 also copies all variables from the goal with each copy of the
> template and restores these. That has its own problems.
>
> Cheers --- Jan
>
>> Example:
>>
>> | ?-L0 =[X,y(Y),z],findall(E,member(E,L0),L). L0 =[X,y(Y),z], L
>> =[_G2443,y(_G2438),z]. |
>>
>> If so, is there any other built-in I could use, or is coding a
>> custom predicate the only way to keep bindings?
>
>
>

[Julio Di Egidio]

On Thursday, September 15, 2016 at 10:42:27 AM UTC+2, Jan Wielemaker wrote:

On 15/09/16 10:20, Julio Di Egidio wrote:
> On Thursday, September 15, 2016 at 9:26:27 AM UTC+2, Jan Wielemaker
> wrote:
>
> On 09/15/2016 09:15 AM, Julio Di Egidio wrote:
>> Hello guys, a question if you won't mind:
>>
>> I am trying to collect terms with findall but I am losing the
> bindings.
>>
>> Does findall/[3-4] duplicate terms before collecting?
>
> Yes.  There isn't much else it can do.  In *theory* it could share
> terms that predate the findall call and are not instantiated by it.
> Finding that a term predates a call isn't too hard (it is just
> further down the stack), but figuring out whether or not it has been
> instantiated will be rather hard (=slow).  Without that, copying is
> the only option.
>
> I have had look into pl-bag.c, but the code itself does not make
> clear why that must be the case, i.e. why findall cannot just keep
> generated terms as they are. Any way you can explain it, I mean
> unless it requires writing a little treatise?  :)

It is fairly easy: after the goal generates a solution, the system
backtracks for the next solution.  Any term created while running
the goal is thus destroyed.  If the term is older than the findall
goal this is of course not true, but any instantiation done by the
goal will be lost.

Ah, yes: I was confused as I thought findall was lower level than that, i.e.

-say- that it could simply collect links to terms (as per the template) as

they are after each success of the generator, but OK...

In general, variations of findall(X, member(X, List), XL) is not a
very good idea.  You typically can get the same results using
library(apply) and library(yall) without copying anything.  That
is often faster and at least as important it avoids all semantic
issues around copying (and saves memory).

Thank you, that's indeed better than a custom predicate (and I was not

aware of library(yall) at all).

Julio

[Julio Di Egidio]

It now occurs to me that this can be "worked around", the essential idea
being that of unifying any new terms with the original ones after copy (or
duplication):

?- X = z(Z), copy_term(X, Y), writeln([X,Y]), X == Y.
[z(_G728),z(_G985)]
false.

?- X = z(Z), copy_term(X, Y), Y = X, writeln([X,Y]), X == Y.
[z(_G770),z(_G770)]
X = Y, Y = z(Z).

?- X = z(Z), duplicate_term(X, Y), Y = X, writeln([X,Y]), X == Y.
[z(_G800),z(_G800)]
X = Y, Y = z(Z).

The example I gave earlier becomes:

?- L0 = [X, y(Y), z], findall(E, member(E, L0), L), L = L0.
L0 = L, L = [X, y(Y), z].

Cheers,

Julio

[Julio Di Egidio]

On Thursday, September 15, 2016 at 4:12:47 PM UTC+2, Julio Di Egidio wrote:

On Thursday, September 15, 2016 at 9:15:56 AM UTC+2, Julio Di Egidio wrote:

Hello guys, a question if you won't mind:

I am trying to collect terms with findall but I am losing the bindings.

Does findall/[3-4] duplicate terms before collecting?

Example:

?- L0 = [X, y(Y), z], findall(E, member(E, L0), L).
L0 = [X, y(Y), z],
L = [_G2443, y(_G2438), z].

If so, is there any other built-in I could use, or is coding a custom predicate the only way to keep bindings?

It now occurs to me that this can be "worked around", the essential idea
being that of unifying any new terms with the original ones after copy (or
duplication):

Sorry, now I do not understand why that happens with copy_term.  The docs for

copy_term/2, as copy_term(+In, -Out), say:

  Create a version of In with renamed (fresh) variables and unify
  it to Out.

Shouldn't we *not* need unification after copy if that is the case?

Thanks,

Julio

[Jan Wielemaker]

On 15/09/16 17:13, Julio Di Egidio wrote:
> On Thursday, September 15, 2016 at 4:12:47 PM UTC+2, Julio Di Egidio wrote:
>
> On Thursday, September 15, 2016 at 9:15:56 AM UTC+2, Julio Di Egidio
> wrote:
>
> Hello guys, a question if you won't mind:
>
> I am trying to collect terms with findall but I am losing the
> bindings.
>
> Does findall/[3-4] duplicate terms before collecting?
>
> Example:
>
> |

> ?-L0 =[X,y(Y),z],findall(E,member(E,L0),L).
> L0 =[X,y(Y),z],

> L =[_G2443,y(_G2438),z].

> |
>
> If so, is there any other built-in I could use, or is coding a
> custom predicate the only way to keep bindings?
>
>
> It now occurs to me that this can be "worked around", the essential idea
> being that of unifying any new terms with the original ones after
> copy (or
> duplication):
>
>
> Sorry, now I do not understand why that happens with copy_term. The
> docs for
> copy_term/2, as copy_term(+In, -Out), say:
>
> Create a version of In with renamed (fresh) variables and unify
> it to Out.
>
> Shouldn't we *not* need unification after copy if that is the case?

I have little clue what you mean. You can achieve preservation of
variables. Bagof/3 does this. It is implemented on top of findall/3,
so you can look at the source. It also splits the set of solutions
according to variable bindings for variables that are not existentially
qualified and do not appear in the template. You could role a version
that only restores the binding based on the code for bagof/3. Still,
I don't think these are the right primitives for transforming and/or
selecting terms from a list.

Cheers --- Jan

[Julio Di Egidio]

Never mind, I was just misreading the docs: these say the new term is unified

with Out, I was reading it is unified with In, i.e. with the original term...

 You can achieve preservation of
variables.  Bagof/3 does this.  It is implemented on top of findall/3,
so you can look at the source.  It also splits the set of solutions
according to variable bindings for variables that are not existentially
qualified and do not appear in the template.  You could role a version
that only restores the binding based on the code for bagof/3.  Still,
I don't think these are the right primitives for transforming and/or
selecting terms from a list.

No prob, I too think those primitives are fine.  OTOH, I don't think my case

is that peculiar either: I am using term expansion to find some calls to a

predicate and rewrite this as calls to some other predicate, and I need to

keep the variable bindings.  Anyway, thanks again, my initial problem is

indeed solved.

Cheers,

Julio