Is there a smarter way to use maplist?

[kaitainjones]

I've never been sure if I've been missing something really obvious with maplist. If I had the predicate 

subtract( X, Y, Result )

where Y was subtracted from X, is there a way in which I could e.g. subtract the value 3 from each element in a list using maplist/3? If I were using the predicate

subtract_first_from_second( First, Second, Result )

...it would be easy enough to accomplish the following:

?- maplist( subtract_first_from_second( 3 ), [10,20,30], Out ).

Out = [7, 17, 27].

But is there a way I can achieve the same outcome using the first version of the predicate, i.e. without having a rewritten version of the predicate, in which the parameter I want to be a fixed value in the maplist comes first? (Obviously I could generate a list of 3s and use that as the second list arg in a maplist/4, but that would kinda suck.)

[m00nlight]

Just use plus/3 predicate can do the work,

?- maplist(plus(-3), [10, 20, 30], Out).

Out = [7, 17, 27].

?-

--
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.
Visit this group at http://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

--

--m00nlight

[Kaitain Jones]

Sorry, to clarify, that's just an arbitrary example. I don't really care about subtraction; I'm interested in whether or not it's possible to use maplist in a manner where there is less order-dependency on arguments (in a generic sense).

[Wouter Beek]

Hi Kaitain,

I've had this problems as well, since I agree that creating an auxiliary predicate for rearranging the arguments is not quite elegant. Luckily, you can write the argument reordering as an in-line lambda expression. Ulrich Neumerkel has created a very good package for lambda expressions (also useful in many other circumstances): http://swi-prolog.org/pack/list?p=lambda

---
Cheers!,
Wouter Beek.

E-mail: w.g.j...@vu.nl
WWW: www.wouterbeek.com
Tel.: 0647674624

On Wed, Jul 23, 2014 at 4:32 AM, Kaitain Jones <kaitai...@gmail.com> wrote:

Sorry, to clarify, that's just an arbitrary example. I don't really care about subtraction; I'm interested in whether or not it's possible to use maplist in a manner where there is less order-dependency on arguments (in a generic sense).

On Tue, Jul 22, 2014 at 7:30 PM, m00nlight <dot.wa...@gmail.com> wrote:

[Carlo Capelli]

1 ?- [library(lambda)].

true.

2 ?- maplist(\X^Y^(Y is X-3), [10,20,30], Out).

Out = [7, 17, 27].

Beware to efficiency...

Also, I remember it was rather easy to me to write wrong syntax.
At the time, was rather difficult to debug, but I noticed that the debugger has improved a lot recently.

Carlo

[Jan Wielemaker]

On 07/23/2014 08:11 AM, Carlo Capelli wrote:
> 1 ?- [library(lambda)].
>
> true.
>
>
> 2 ?- maplist(\X^Y^(Y is X-3),[10,20,30],Out).
>
> Out = [7, 17, 27].
>
>
> Beware to efficiency...

... and don't take this too lightly:

==
:- use_module(library(lists)).
:- use_module(library(lambda)).
:- use_module(library(apply_macros)).

t1 :-
numlist(1, 1 000 000, L),
time(maplist(plus(-3), L, _Out)).

t2 :-
numlist(1, 1 000 000, L),
time(maplist(\X^Y^(Y is X-3), L, _Out)).
==

11 ?- t1.
% 2,000,004 inferences, 0.126 CPU in 0.126 seconds (100% CPU, 15840367 Lips)
true.

12 ?- t2.
% 10,000,003 inferences, 1.462 CPU in 1.462 seconds (100% CPU, 6840556 Lips)
true.

Of course, if the called predicate is expensive, it doesn't matter
much ...

Cheers --- Jan

[Kaitain Jones]

Huh. Wow, yes, this is very useful. Thanks, folks.

[Jonathan Avery]

I have actually thought up my own solution to this recently :D.
I made a general mapping predicate I called myMap:

doMember(Relation,MemberOfList,List,Result) :-
  member(MemberOfList,List), call(Relation).
myMap(Relation,MemberOfList,List,Result,ResultList):-
  findall(Result,doMember(Relation,MemberOfList,List,Result),ResultList).

And here is an example of a query:
  myMap(concat('a ', X, Y), Y, ['a dog', 'a cat'], X, Solutions).
which yeilds:
  Solutions = [dog, cat].


As you can probably see, this can be used more arbitrarily as in:
  myMap(findall([A,B],concat(A,B,C),X), C, [a,ab,abc], X, Solutions).
which yeilds:
  Solutions = [[['', a], [a, '']], [['', ab], [a, b], [ab, '']], [['', abc], [a, bc], [ab, c], [abc, '']]].

I hope you like this! :D

[Jan Wielemaker]

On 07/24/2014 07:55 AM, Jonathan Avery wrote:
> I have actually thought up my own solution to this recently :D.
> I made a general mapping predicate I called myMap:
>
> doMember(Relation,MemberOfList,List,Result) :-
> member(MemberOfList,List), call(Relation).
> myMap(Relation,MemberOfList,List,Result,ResultList):-
> findall(Result,doMember(Relation,MemberOfList,List,Result),ResultList).
>
> And here is an example of a query:
> myMap(concat('a ', X, Y), Y, ['a dog', 'a cat'], X, Solutions).
> which yeilds:
> Solutions = [dog, cat].
>
>
> As you can probably see, this can be used more arbitrarily as in:
> myMap(findall([A,B],concat(A,B,C),X), C, [a,ab,abc], X, Solutions).
> which yeilds:
> Solutions = [[['', a], [a, '']], [['', ab], [a, b], [ab, '']], [['',
> abc], [a, bc], [ab, c], [abc, '']]].
>
> I hope you like this! :D

It is one of the many things one can do. There are several issues with
this. One is that it is failure driven. That has two disadvantages:
you cannot combine this with constraints (in most cases) and a possible
failure of your mapping relation just causes the element to be dropped
silently. The other is that findall/3 needs to copy the result, which
can be painful if it concerns a large term.

You can implement the above as a loop, but that requires a copy of the
mapping goal for each iteration to get fresh copies of the variables.
That is the same problem that library(lambda) is suffering from.

Other alternatives are list comprehension (B-Prolog) and logical loops
(ECLiPSe and SICStus). These have their own logical issues as pointed
out by Ulrich Neumerkel on this list, but the advantage is that they
can be compiled by goal-expansion, so there is no runtime overhead.

Maybe we should provide all these alternatives as packs. Anyone? I'm
still hoping that a really good solution comes along: one that does not
do backtracking, no copy_term, is readable, can be compiled and
meta-called and provides good performance. I don't think there is a
proof that this cannot exists. I think it can, but we would need
something more flexible than call/N. Call/N is the basis of maplist/N,
which has all these nice properties, except that it insists on adding
the fresh variables at the end of the arguments.

Cheers --- Jan

P.s. Your solution can also be compiled. Possibly the combination
of compilation and a copy-term/loop based implementation of
this interface is a good compromise? Comments?

> On Wednesday, July 23, 2014 11:35:31 AM UTC+12, kaitainjones wrote:
>
> I've never been sure if I've been missing something really obvious
> with maplist. If I had the predicate
>
> subtract( X, Y, Result )
>
> where Y was subtracted from X, is there a way in which I could e.g.
> subtract the value 3 from each element in a list using maplist/3? If
> I were using the predicate
>
> subtract_first_from_second( First, Second, Result )
>
> ...it would be easy enough to accomplish the following:
>
> ?- maplist( subtract_first_from_second( 3 ), [10,20,30], Out ).
> Out = [7, 17, 27].
>
> But is there a way I can achieve the same outcome using the first
> version of the predicate, i.e. without having a rewritten version of
> the predicate, in which the parameter I want to be a fixed value in
> the maplist comes first? (Obviously I could generate a list of 3s
> and use that as the second list arg in a maplist/4, but that would
> kinda suck.)
>

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

[Paulo Moura]

The missing optimization bit here is to automatically generate an auxiliary predicate for the lambda expression (whenever possible, of course). Logtalk does it (using its library meta-compiler, which is the equivalent to your library apply). On my old laptop:

?- t1.
% 3,000,038 inferences, 0.570 CPU in 0.683 seconds (83% CPU, 5264675 Lips)
true.

?- t2.
% 4,000,038 inferences, 0.616 CPU in 0.692 seconds (89% CPU, 6496827 Lips)
true.

Note that in t1 we're calling a built-in predicate (plus/3) while in t2 we're calling a user predicate (the auxiliary predicate) that calls a built-in predicate (is/2), hence the difference in the number of inferences.

Cheers,

Paulo

-----------------------------------------------------------------
Paulo Moura
Logtalk developer

Email: <mailto:pmo...@logtalk.org>
Web: <http://logtalk.org/>
-----------------------------------------------------------------

[Paulo Moura]

P.S. Above t1 and t2 are also timing the generation of the 1000000 elements list, hence the difference in the number of inferences when compared with the Prolog version.

[Paulo Moura]

Fixed example source code to avoid timing the list generation:

:- object(benchmarks).

:- use_module(prolog_satistics, [time/1]).

:- public(plus/0).
plus :-
integer::sequence(1, 1000000, L),
time(meta::map(plus(-3), L, _Out)).

:- public(lambda/0).
lambda :-
integer::sequence(1, 1000000, L),
time(meta::map([X,Y]>>(Y is X-3), L, _Out)).

:- end_object.

?- set_logtalk_flag(optimize, on), logtalk_load(library(meta_compiler_loader)), use_module(library(statistics)), logtalk_load(benchmarks, [hook(meta_compiler)]).
...
% (0 warnings)
true.

?- benchmarks::plus.
% 2,000,003 inferences, 0.412 CPU in 0.574 seconds (72% CPU, 4856911 Lips)
true.

?- benchmarks::lambda.
% 3,000,001 inferences, 0.470 CPU in 0.577 seconds (81% CPU, 6380646 Lips)
true.

[Jan Burse]

For a smaller list, and on 64-bit, I get different results:

?- findall(N,between(1,100000,N),L), time(map(plus(-3),L,R)), fail.
% 200,000 inferences, 0.047 CPU in 0.042 seconds (111% CPU, 4273477 Lips)

?- findall(N,between(1,100000,N),L), time(map(\X^Y^(Y is X-3),L,R)), fail.
% 1,000,000 inferences, 0.172 CPU in 0.185 seconds (93% CPU, 5827468 Lips)

Here the factor between lambda and non lambda is only around 4.5 (0.185 seconds / 0.042 seconds)
For a longer list I get a much bigger factor:

?- findall(N,between(1,1000000,N),L), time(map(plus(-3),L,R)), fail.
% 2,000,000 inferences, 0.218 CPU in 0.226 seconds (97% CPU, 9157450 Lips)

?- findall(N,between(1,1000000,N),L), time(map(\X^Y^(Y is X-3),L,R)), fail.
% 10,000,000 inferences, 2.340 CPU in 2.402 seconds (97% CPU, 4273477 Lips)

The factor is now 10.6 (2.402 seconds / 0.226 seconds).
My speculation, this could be a garbage collection effect.

For another Prolog system and another lambda library I see the same
effect, much more pressure on the garbage collection when the list
is long. Probably constantly reaching some watermark so that the
system is more busy with garbage collection than solving the problem.

The lambda solution might reach the watermark more often, since
the abstract term, when applied, creates a term copy. Resulting
in more traversals of the whole memory, even if only little memory
is reclaimed. Resulting in a doubled almost trippled factor than
usual (10.6 versus 4.5).

So I am not sure whether the conlcusion is now to avoid library(lambda)
or whether a special aux predicate compilation is needed. For small
lists it looks not so critical for me.

Just some guesses.

Bye

[Jonathan Avery]

Very interesting. :)
Is the hope that maybe we could take advantage of copy_term/2 to avoid duplicating ground terms with findall?
(Just trying to understand the goal of using copy_term)
When you say loop based do you mean a minimally recursive goal to avoid using findall?
If you do mean that, wouldn't that still suffer from the problems you mentioned below?

"You can implement the above as a loop, but that requires a copy of the
mapping goal for each iteration to get fresh copies of the variables.
That is the same problem that library(lambda) is suffering from. "

> <mailto:swi-prolog+unsub...@googlegroups.com>.

[Jan Wielemaker]

On 07/25/2014 08:15 AM, Jonathan Avery wrote:
> Very interesting. :)
> Is the hope that maybe we could take advantage of copy_term/2 to avoid
> duplicating ground terms with findall?
> (Just trying to understand the goal of using copy_term)
> When you say loop based do you mean a minimally recursive goal to avoid
> using findall?
> If you do mean that, wouldn't that still suffer from the problems you
> mentioned below?
>
> "You can implement the above as a loop, but that requires a copy of the
> mapping goal for each iteration to get fresh copies of the variables.
> That is the same problem that library(lambda) is suffering from. "

You can implement it like this:

my_map(_, _, [], _, []).
my_map(G, X, [X1|T0], Y, [Y1|T]) :-
copy_term(t(G,X,Y), t(G1,X1,Y1)),
call(G1),
my_map(G, X, T0, Y, T).

Now, the size of the output terms no longer matters, the entire
goal fails if calling the mapping goal fails for some value and
as computation only goes forwards, you can do things such as imposing
constraints, etc. The price you pay is creating a copy of G every
time to get a fresh set of variables for the next iteration. If you
don't do that, calling G will bind X and Y, and the next iteration
will only work if there is a consistent X and Y for the next solution.

Cheers --- Jan

P.s. A full implementation typically adds an intermediate clause
to improve on the argument order for better indexing and avoid
creating the first t/3 term each iteration:

:- meta_predicate my_map(0,?,?,?,?).

my_map(G, X, LX, Y, LY) :-
my_map_aux(LX, LY, t(G,X,Y)).

my_map_aux([], [], _).
my_map_aux([X1|T0], [Y1|T], G) :-
copy_term(G, t(G1,X1,Y1)),
call(G1),
my_map_aux(T0, T, G).

> > an email to swi-prolog+...@googlegroups.com <javascript:>
> > <mailto:swi-prolog+...@googlegroups.com <javascript:>>.

> > Visit this group at http://groups.google.com/group/swi-prolog

> <http://groups.google.com/group/swi-prolog>.

> > For more options, visit https://groups.google.com/d/optout

> <https://groups.google.com/d/optout>.

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

[Paulo Moura]

The full optimization, of course, is when we get rid of both the copy_term/2 call and the meta-call (call/1) by introducing an auxiliary predicate. For example, going from (in the code I posted earlier):

map([X,Y]>>(Y is X-3), L, _Out)

to (with non-relevant details abstracted):

lambda_goal(X, Y) :-
Y is X-3.

map_lambda_goal([], []).
map_lambda_goal([X|XX], [Y|YY]) :-
lambda_goal(X, Y),
map_lambda_goal(XX, YY).

In this particular case where the lambda goal is just a call to a built-in predicate, the specialization of the map/3 call can be further optimized by in-lining the lambda goal:

map_lambda_goal([], []).
map_lambda_goal([X|XX], [Y|YY]) :-
Y is X-3,
map_lambda_goal(XX, YY).

which is essentially the same code that you would be writing by hand without using list mapping meta-predicates and lambda expressions. These optimizations can be (and have been) automated. E.g. the SWI-Prolog "apply" library already creates the specialization of frequently used meta-predicates such as maplist/N. The Logtalk "meta_compiler" library does both the specialization of frequently used meta-predicates and the generation of the auxiliary predicates (including for lambda expressions).

Maybe the "apply" library can be extended with an hook predicate to (help) compile the goal that is being iterated and then libraries such as "lambdas" can provide a definition for this hook predicate?