maplist and friends

[Attila Bartha]

i'm experimenting with variations on maplist and friends.
i would like more control on which arguments of the predicate will be unified with the elements of the lists.
i have came up with the following:

vmaplist(Pred, LA) :-
        term_variables(Pred, VL),
        vmaplist_a(Pred, VL, LA).

vmaplist_a(_, _, []) :- !.
vmaplist_a(Pred, VL, [A|As]) :-
        copy_term((Pred, VL), (Q, [A])),
        call(Q),
        vmaplist_a(Pred, VL, As).

vmaplist(Pred, LA, LB) :-
        term_variables(Pred, VL),
        vmaplist_a(Pred, VL, LA, LB).

vmaplist_a(_, _, [], []) :- !.
vmaplist_a(Pred, VL, [A|As], [B|Bs]) :-
        copy_term((Pred, VL), (Q, [A, B])),
        call(Q),
        vmaplist_a(Pred, VL, As, Bs).

in vmaplist/2,3 the (copy of the) free variable(s) which appear in Pred will be successively unified with the elements of the list(s) and (a copy of) Pred will be called.

in vmaplist_a Pred can have more free variables than the number of lists, and an additional list in the 2-nd position of vmaplist_a holds the vars which will be unified with the elems of the lists.

some examples:

:- vmaplist(X<10, [1,2,3]).
true.

:- vmaplist(A=B, [1,2,3], L).
L = [1,2,3].

:- vmaplist(A-B=C, [1,3,4,2], [foo,bar,baz,kix], L),
keysort(L, S),
vmaplist(A=B-C, S, X, Y).
L = [1-foo, 3-bar, 4-baz, 2-kix],
S = [1-foo, 2-kix, 3-bar, 4-baz],
X = [1, 2, 3, 4],
Y = [foo, kix, bar, baz].

vmaplist_a((numlist(1,N,L),format('~w ~w~n',[N, L])), [N], [1,3]).
1 [1]
3 [1, 2, 3]

vmaplist has about half the speed of maplist.
i suppose a lot of garbage is created because of copy_term.

vmaplist relies on the observation that term_variables gives the free vars in the order in which they appear in the text of Pred.
i have tested this on cases like :
  term_variables(pred(A, foo(B)), L). =>  L= [A,B]).
  term_variables(pred(foo(A), B)), L). => L = [A,B]).
it seems to be ok, but i guess is implementation specific, so it might be a problem.

i would like to hear your comments on this.
maybe other names for 'vmaplist', 'vmaplist_a' ?

-attoparsec-


      ____________________________________________________________________________________
Be a better friend, newshound, and
know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Ulrich Neumerkel]

On Saturday 19 Apr 2008 02:00:47 Attila Bartha writes:
> i'm experimenting with variations on maplist and friends.
> i would like more control on which arguments of the predicate will be unified with the elements of the lists.

Your vmaplist does not give you more control, but less.  The variables
occurring dynamically at the time of calling vmaplist in Pred are now
local.  For instance, vmaplist cannot describe maplist(=(_), L); a
list with all elements equal.

Admittedly, the higher order style of maplist/2 is not everybody's
turf.  You gave vmaplist(X<10, [1,2,3]) as an example, which
reformulates to maplist(>(10), [1,2,3]).  Here, we have luck, as a
substitute for the original </2 is available that slides the variable
into the last argument.  In general, define an auxiliary predicate
where the last arguments are substituted.  A more lambdaoid notation
would help, but there is no consensus on this - yet.

Your definition cuts choices incorrectly resulting in inconsistent
behaviour: While ?- Xs = [1], maplist(=(1),Xs). suceeds,
?- maplist(=(1),Xs), Xs = [1]. incorrectly fails.  Just remove those
unlucky adornments.

If you insist on finite lists, state must_be(list,L) in the beginning.
Even then the choice cut is useless and costs time and attention.

The exact variable order for term_variables/2 is stated in the manual.

Accelerate the internal list predicates taking their 3rd argument first.

Surprised by you reporting a factor of two in slowdown, I remeasured
times obtaining a factor of 10:

f.pl contains additionally rule p(L) :- maplist(<(0),L). to trigger
specialization - as it would be implicitly the case in a bigger
program.

My .plrc (or pl.ini) contains as first line
:- use_module(library(apply_macros)).
to accelerate maplist.  Also clpfd and DCGs profit significantly from
that line.

g1> pl -O -s f.pl -t halt -g 'time(forall((numlist(1,200,L),between(1,10000,_)), vmaplist(0<X,L))).'
...
%  library(apply_macros) compiled into apply_macros 0.00 sec, 69,416 bytes
...
% /nfs/ahome/ulrich/.plrc compiled 0.03 sec, 602,344 bytes
% f.pl compiled 0.00 sec, 3,536 bytes
% 8,030,408 inferences, 2.70 CPU in 2.71 seconds (100% CPU, 2974225 Lips)
g1> pl -O -s f.pl -t halt -g 'time(forall((numlist(1,200,L),between(1,10000,_)), maplist(<(0),L))).'
...
%  library(apply_macros) compiled into apply_macros 0.00 sec, 69,416 bytes
...
% /nfs/ahome/ulrich/.plrc compiled 0.03 sec, 602,344 bytes
% f.pl compiled 0.00 sec, 3,536 bytes
% 2,010,408 inferences, 0.26 CPU in 0.27 seconds (98% CPU, 7732338 Lips)

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Attila Bartha]

--- On Mon, 4/21/08, Ulrich Neumerkel <ulrich@...> wrote:

> The variables occurring dynamically at the time of calling vmaplist in
> Pred are now local.  For instance, vmaplist cannot describe
> maplist(=(_), L); a list with all elements equal.

the locality of variables is one thing i want from vmaplist.
if i want a free var in Pred to share with all elements of the list, i still have maplist.

> In general, define an auxiliary predicate where the last arguments
> are substituted.  

defining auxiliary predicates is exactly what i want to avoid.

> A more lambdaoid notation would help, but there is no consensus
> on this - yet.

i'm interested in proposals. can you point me to some resources ?
the 2nd argument of vmaplist_a is in fact a kind of lambda.
vmaplist just builds this 'lambda-list' and passes it to vmaplist_a.

> Your definition cuts choices incorrectly resulting in
> inconsistent behaviour

you are right, the cut is useless.

> Surprised by you reporting a factor of two in slowdown, I
> remeasured times obtaining a factor of 10

you are right again. i rerun the tests and i got 3 to 5 time speed drop without optimization and apply_macros.
(looking again on my tests i discovered that vmaplist required 2 x more *inferences* - i think that's why i said half a speed. blunder. )

however, vmaplist can be macroed out just as maplist.

maybe a syntax like in bagof for 'lambda-vars' ?
vmaplist(somepred(^X, a, ^Y, 2), A, B).
then the macro expander can define an aux predicate where the ^-marked vars are moved in the last positions.

-attoparsec-



      ____________________________________________________________________________________
Be a better friend, newshound, and
know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Samer Abdallah]

On 21 Apr 2008, at 03:59, Bartha Attila wrote:

> i'm interested in proposals. can you point me to some resources ?
> the 2nd argument of vmaplist_a is in fact a kind of lambda.
> vmaplist just builds this 'lambda-list' and passes it to vmaplist_a.
>

I've been using something like this - it's based on a replacement  
call-like
predicate that accepts a lambda term as the first argument. An example
of a lambda term would be something like:
        ( \(X,Y,Z) :- foo(Z,a), bar(b,X-Y) )
ie, it's a binary term Head :- Body, where Head is an n-ary term
with '\' as the functor, and Body is a goal. It behaves more or less as
if a dummy predicate had been defined
        dummy(X,Y,Z) :-
                foo(Z,a),
                bar(b,X-Y).

I say 'more or less' because if there are free variables in the body,
they must instantiate to a single value in the calling context
        ?- maplist( \(A):-A=B, [a,a,a,a]).
succeeds with B=a while
        ?- maplist( \(A):-A=B, [a,b,a,a]).
fails. However, the body can include an explicit existential
quantification so that, eg
        ?- maplist( \(A):- B^(A=B), [a,b,c,d]).
succeeds leaving B unbound.

Implementation is based on a replacement call/N predicate;
without the obvious bits and without the extra clauses to handle
existential quantification, it looks like this:

        maplist(P,[A|AX]) :- call(P,A), maplist(P,AX).
        maplist(P,[A|AX],[B|BX] :- call(P,A,B), maplist(P,AX,BX).
        % etc.

        call(P,A) :- mkcall(P, \(A), G), call(G).
        call(P,A,B) :- mkcall(P, \(A,B), G), call(G).
        call(P,A,B,C) :- mkcall(P, \(A,B,C), G), call(G).
        % etc.

        mkcall(Head:-Body,Args,Goal) :- copy_term(Head:-Body,Args:-Goal).


- Samer




------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Ulrich Neumerkel]

On Monday 21 Apr 2008 12:48:13 Samer Abdallah wrote:
> ...   However, the body can include an explicit existential
> quantification so that, eg
>         ?- maplist( \(A):- B^(A=B), [a,b,c,d]).
> succeeds leaving B unbound.

What about

?- B = a, maplist( \(A):- B^(A=B), [a,b,c,d]).

which should succeed (or produce an error), since the B at the top is
different.  To treat this correctly quite a lot would have to be
reconsidered.  And all this, just to avoid inventing a new name -
which certainlich is cumbersome.

By the same token, I do not see how macro-expansion could be
implemented for this construct in a way similar to maplist.  That is,
without user-visible scope changes of variables.  The same objection
holds for Attila Bartha's vmaplist.

The cleanest way I see (but do not like) is to put most of the lambda
into a string or other ground structure thereby avoiding scoping
problems (and complicating variables with global scope).  The runtime
overheads would be negligible as expansion would usually occur at
compile time.  But the overheads for reading and writing hurt.
Languages with scoping have a pile of restrictions Prolog people do
not like either.  Well, maybe - there is a better way? Qui sait!

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Samer Abdallah]

On 21 Apr 2008, at 14:33, Ulrich Neumerkel wrote:
> On Monday 21 Apr 2008 12:48:13 Samer Abdallah wrote:
>> ...   However, the body can include an explicit existential
>> quantification so that, eg
>>         ?- maplist( \(A):- B^(A=B), [a,b,c,d]).
>> succeeds leaving B unbound.
>
> What about
>
> ?- B = a, maplist( \(A):- B^(A=B), [a,b,c,d]).

As it stands, my code would see this as
        maplist( \(A) :- a^(A=a), [a,b,c,d])
It would ignore the existential quantification since it
contains no variables, and therefor fail overall since some
elements are not 'a'. If I was being more careful I would
probably make any ground term in the existential
quantification produce an error. Overall, it's not a lot of
code, though I will admit that the existential variable
handling code isn't pretty since it needs to manipulate
sets of uninstantiated variables.

>
> which should succeed (or produce an error), since the B at the top is
I'm not sure why you would expect it to succeed - perhaps
you are reading the existential quantification differently from
me? My interpretation is that the existential quantification
is to make it behave exactly like an auxiliary predicate defined
in the usual way:
        aux(A) :- A=B
which has the implicit quantification, ie, it means
        (exists B . A=B)  => aux(A)
> different.  To treat this correctly quite a lot would have to be
> reconsidered.  And all this, just to avoid inventing a new name -
> which certainlich is cumbersome.
>
> By the same token, I do not see how macro-expansion could be
> implemented for this construct in a way similar to maplist.  That is,
Fair enough - I don't really know anything about macro expansion -
my version runs in a meta-interpreter so it's dog slow whatever
i do :)


> without user-visible scope changes of variables.  The same objection
> holds for Attila Bartha's vmaplist.
>
> The cleanest way I see (but do not like) is to put most of the lambda
> into a string or other ground structure thereby avoiding scoping
This addresses the heart of the problem which is that a lambda
expression is a term that needs to refer to variables; that is,  
variables
are used as part of the object language - but in this case they need to
be 'lambda variables', not Prolog variables; that is, they need to be  
ground
objects which denote 'variables in the language of lambda expressions'.
The fact that Prolog does such a good job of being its own meta-language
makes it easy to get into the sort of mess where Prolog variables are
used as stand-ins for variables which strictly belong to a different
level and hence we need to use all sorts of non-logical Prolog code to
manipulate them. So one option would be to use a certain set of ground
terms to denote variables, eg a unary operator/functor like ?/1:
        maplist(  \(?x) :- ?y ^(?x = ?y), [a,b,c,d]).
But then it all starts to get a bit heavy and maybe it would be better
just to define an auxiliary predicate after all...

Samer

> problems (and complicating variables with global scope).  The runtime
> overheads would be negligible as expansion would usually occur at
> compile time.  But the overheads for reading and writing hurt.
> Languages with scoping have a pile of restrictions Prolog people do
> not like either.  Well, maybe - there is a better way? Qui sait!


------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Ulrich Neumerkel]

On Monday 21 Apr 2008 16:06:27 Samer Abdallah wrote:

> On 21 Apr 2008, at 14:33, Ulrich Neumerkel wrote:
> > On Monday 21 Apr 2008 12:48:13 Samer Abdallah wrote:
> >> ...   However, the body can include an explicit existential
> >> quantification so that, eg
> >>         ?- maplist( \(A):- B^(A=B), [a,b,c,d]).
> >> succeeds leaving B unbound.
> >
> > What about
> >
> > ?- B = a, maplist( \(A):- B^(A=B), [a,b,c,d]).
> ...
> > which should succeed (or produce an error), since the B at the top is
> I'm not sure why you would expect it to succeed - perhaps
> you are reading the existential quantification differently from
> me? My interpretation is that the existential quantification
> is to make it behave exactly like an auxiliary predicate defined
> in the usual way:
>         aux(A) :- A=B
> which has the implicit quantification, ie, it means
>         (exists B . A=B)  => aux(A)

Yes, so the B outside in B = a must be something different, entirely
unrelated to the quantified B.  It is the same as renaming the
internal B to B1.

Remark that you will succed for

?- maplist( \(A):- B^(A=B), [a,b,c,d]), B = a

as well, which would be consistent with the success of

?- B = a, maplist( \(A):- B^(A=B), [a,b,c,d]).

As we have here a pure program the conjunction G, H should be the same
as H, G.  You might have issues about termination and similar to
settle, but otherwise there cannot be any differences.

The most sensible would be some static checking, but there the
difficulties start...

Note that ensuring B being a variable is not sufficient, as it may share
with other variables in conflicting scope.

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Kuniaki Mukai]

(Sorry for my poor English.)

Interesting thread !

For years, I have written several versions of predicate eval
including lambda calculus on top of SWI-Prolog for fun.  In order to
keep theoretical soundness of lambda ( beta ) calculus, the eval
refreshes bound variables for every application !

Here are several sample calls for the eval predicate,
where \ for lambda abstraction,   \\ for Prolog call,
and  @ for  application.

?- eval((x\x)@ (y\y), V).
V =  y\y
?- eval(((X\X)@ (Y\Y))@ hello, V).
V =  hello
?- eval([x,y]\[x,y])@1@2, V).
V = [1, 2]
?- maplist(x\ [x], [a,b,c], V).
V= [[a], [b], [c]]
?- maplist(x\y\(y @ x), [a,b,c], [x\[x], x\[x,x], x\[x,x,x]], V)
V =  [[a], [b, b], [c, c, c]]
?- maplist([x,y,z]\\ append(x,z,y), [[a],[b]], [[a,b,c], [b,a,c]], V).
V = [[b, c], [a, c]].

If interested, you can find many more samples at the page
http://web.sfc.keio.ac.jp/~mukai/mathcgi/fpop-sample.html,
which was created by a simple script written in SWI-Prolog
using the eval

I should say the current code of the eval predicate is, of course,
very slow.  However, I feel lambda notation in Prolog is handy
and useful for daily use of Prolog where efficiency
does not matter.

Learning about 'apply_macro' library in this thread, now I think the
library can be extended to treat these lambda expressions as macros.
I think so because at least for my purpose,  lambda expressions
are just a handy macro which is easily rewritten by hand
into the standard Prolog in a straightforward way.

Kuniaki Mukai


On 2008/04/22, at 8:40, Ulrich Neumerkel wrote:

> On Monday 21 Apr 2008 16:06:27 Samer Abdallah wrote:
>> On 21 Apr 2008, at 14:33, Ulrich Neumerkel wrote:
>>> On Monday 21 Apr 2008 12:48:13 Samer Abdallah wrote:
>>>> ...   However, the body can include an explicit existential
>>>> quantification so that, eg
>>>>        ?- maplist( \(A):- B^(A=B), [a,b,c,d]).
>>>> succeeds leaving B unbound.
>>>
>>> What about
>>>
>>> ?- B = a, maplist( \(A):- B^(A=B), [a,b,c,d]).
>> ...
>>> which should succeed (or produce an error), since the B at the top  
>>> is
>> I'm not sure why you would expect it to succeed - perhaps
>> you are reading the existential quantification differently from
>> me? My interpretation is that the existential quantification
>> is to make it behave exactly like an auxiliary predicate defined
>> in the usual way:
>>        aux(A) :- A=B
>> which has the implicit quantification, ie, it means
>>        (exists B . A=B)  => aux(A)
>
> Yes, so the B outside in B = a must be something different, entirely
> unrelated to the quantified B.  It is the same as renaming the
> internal B to B1.
>
> Remark that you will succed for
>
> ?- maplist( \(A):- B^(A=B), [a,b,c,d]), B = a
>
> as well, which would be consistent with the success of
>
> ?- B = a, maplist( \(A):- B^(A=B), [a,b,c,d]).
>
> As we have here a pure program the conjunction G, H should be the same
> as H, G.  You might have issues about termination and similar to
> settle, but otherwise there cannot be any differences.
>
> The most sensible would be some static checking, but there the
> difficulties start...
>
> Note that ensuring B being a variable is not sufficient, as it may  
> share
> with other variables in conflicting scope.
>
> ------------
> For further info, please visit http://www.swi-prolog.org/
>
> To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-
> mail>"
> in its body to majordomo@...

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...