Main Page | Report Page

 

  Computers Forum Index » Computer Languages (Prolog) » Query Answering two Ways to Hide Variables...

Author Message
Martin Riener...
Posted: Sat Sep 04, 2010 1:56 pm
 
On 09/04/2010 12:04 AM, Jan Burse wrote:
Quote:
Ulrich Neumerkel schrieb:
Maybe you could go through your approaches and see
how they fit into this?

Well all the approaches yield the same result inside
certain boundaries.

?- maplist(=(X), Xs).
Xs = [] ;
Xs = [X] ;
Xs = [X, X] ;
Xs = [X, X, X] ;
Xs = [X, X, X, X]


Well I guess maplist does not relate to lambda abstraction.
It makes rather use of application and the curried
presentation of functions. So I am not sure whether
its a good example to check the approaches.

In curried representation we roughly have:

((= A) B) gives (= A B)

We do not need to make a detour over

((lambda C (= A C)) B) gives (= A B)

As I have understood maplist/2 it tries to satisfy the
given predicate for all its elements. So we have

(maplist F (B1 ... Bn)) gives (F B1) & ... & (F Bn)

When using (= X) for F, we get indeed:

(= X B1) & ... & (= X Bn)

?- maplist(X+\X^true, Xs).
Xs = [] ;
Xs = [X] ;
Xs = [X, X] ;
Xs = [X, X, X] ;
Xs = [X, X, X, X]

This is not very intuitive since the '=' sign did
disappear. What would for example happen if we
had the following predicate:

swap((X,Y),(Y,X)).

And then:

?- maplist(swap((X,Y)),Xs).
Xs = [] ;
Xs = [(Y,X)] ;
Xs = [(Y,X),(Y,X)] ;

How would you express it with (+\)/2 and (^)/2?

Bye

Hi!

This works for me:

?- consult(lambda).
% lambda compiled into lambda 0.01 sec, 7,492 bytes
true.

?- Xs=[(1,2),(3,4)], maplist(\X^Y^(X=(A,B), Y=(B,A)),Xs,Ys).
Xs = [ (1, 2), (3, 4)],
Ys = [ (2, 1), (4, 3)].


hth Martin
 
Ulrich Neumerkel...
Posted: Sat Sep 04, 2010 5:11 pm
 
Jan Burse <janburse at (no spam) fastmail.fm> writes:
Quote:
Ulrich Neumerkel schrieb:
Maybe you could go through your approaches and see
how they fit into this?

Well all the approaches yield the same result inside
certain boundaries.

The interesting point is to see how they do this exactly.

Quote:
?- maplist(=(X), Xs).
Xs = [] ;
Xs = [X] ;
Xs = [X, X] ;
Xs = [X, X, X] ;
Xs = [X, X, X, X]


Well I guess maplist does not relate to lambda abstraction.

....

Quote:
?- maplist(X+\X^true, Xs).
Xs = [] ;
Xs = [X] ;
Xs = [X, X] ;
Xs = [X, X, X] ;
Xs = [X, X, X, X]

This is not very intuitive since the '=' sign did
disappear.

?- maplist(X+\Y^(X=Y), Xs).

Quote:
disappear. What would for example happen if we
had the following predicate:

swap((X,Y),(Y,X)).

And then:

?- maplist(swap((X,Y)),Xs).
Xs = [] ;
Xs = [(Y,X)] ;
Xs = [(Y,X),(Y,X)] ;

In this case X Y are globally scoped. Thus,
both have to be declared as globals.

Choose one:

?- maplist((X,Y)+\swap((X,Y)), Xs).
?- maplist({X,Y}+\swap((X,Y)), Xs).
?- maplist([X,Y]+\swap((X,Y)), Xs).

?- maplist((X,Y)+\P^swap((X,Y),P), Xs).
?- maplist((X,Y)+\P^swap(P,(X,Y)), Xs).

So the last two queries show cases where
the argument order does not matter.
 
fodor...
Posted: Sat Sep 04, 2010 6:32 pm
 
Very interesting discussion. I think the idea has also a potential for
optimizing the WAM (for Warren Abstract Machine implementations of
Prolog) for the variables that one doesn't care about. If we have
"X^p(X,Y,Z)", then Y and Z are "don't care variables".
One doesn't want to modify the way anonymous variables (_X) are
treated, so I use this term and notation of "don't care variables" for
optimizations in the WAM. The optimization is a bit messy, but I think
the final point is that one can use such "don't care" variables to
infer points where to put cuts automatically.

Lets consider a rule or a query that has don't care variables:
:- X=a, X^p(X,Y), ....

and a bunch of facts:
p(a,b).
....
What's the point to query for all the values of Y, if all we care
about is if it succeeds for a given X or to find out the values of X.
So, one can think about this query as having an implicit cut "!" (see
it as "(X^p(X,Y),!)" if X is bound).
Of course, one doesn't want such automatically inserted cuts to happen
in general (think about how repeat is implemented (repeat. repeat :-
repeat.)), so this "^" just changes the behaviour of Prolog to
something closer to a deductive database.

---
OK. Lets see the first optimization that I mentioned above.
Don't care variables will only exist in registers, but they won't be
passed.
Let's think how to modify the WAM for such queries X^p(X,Y) (Y is
don't care):
- there can be a test in "getcon" to test if the argument is a "don't
care variable", and don't do anything if it is
- getvar will create the reference to itself on the heap - getval
doesn't get changed because it already creates a variable on the local
stack
p(a,X) :- ..., r(...,X,...),...
- getstruct in write mode (because a variable called it writedc (write
don't care mode) => unicon is a no-op, while univar initializes the
local variable)
p(a,g(X,Y)) :- ..., r(X,...),...
in WAM:
getstruct
uni...
uni...

A special case: propagation of don't care variables.
:- X^p(X,Y).
p(X,Y):- q(X,Z), r(Z,Y), s(Z,X).

If it's the last occurrence of the don't care variable and still a
local variable, then is passed down as a don't care.
I think it appears in cases of: projection, negation (for example,
"X^not(reach(X,Y))", that is, from X you cannot reach anything) and in
findall for all the variables that are not collected.

---
Now the second optimization: automatic cut:
:- ..., X=a, X^(p(X,Y);q(X,Y)), ...
if p(X,Y) succeeds, we don't have to come back to check for q(X,Y) or
to look for both p and q to get all Y.

The way that I see it, it should have a cut for X bound:
... ((X^(p(X,Y);q(X,Y))),!).

Another example:
:- ..., X^p(X,Y), ...
p(X,Y):- q(X,Z), r(Z,Y).
r(a,1).
r(a,2).
....
r(a,1000).

When we call r(Z,Y), Z is bound and Y is "don't care var", so, I think
a cut is appropriate.

I remember that once Dr. David Warren mentioned such an optimization
at Stony Brook for anonymous variables, but that it wouldn't be
appropriate because Prolog has an operational semantics that doesn't
fit this optimization (think of the repeat predicate). However, I
think it's good for cases when the user intentionally wants to ignore
certain variables.

Regards,
Paul Fodor
 
Jan Burse...
Posted: Sun Sep 05, 2010 1:47 am
 
Hi

fodor schrieb:
Quote:
Now the second optimization: automatic cut:
:- ..., X=a, X^(p(X,Y);q(X,Y)), ...
if p(X,Y) succeeds, we don't have to come back to check for q(X,Y) or
to look for both p and q to get all Y.

The way that I see it, it should have a cut for X bound:
... ((X^(p(X,Y);q(X,Y))),!).


Well be careful with the ax. Hopefully I have
understood you correctly. Here is an example
where this transformation would not work:

p(a,b).
q(a,c).

?- X^(X=a, (p(X,Y); q(X,Y)), Y=c).

The above query is not the same as:

?- X^(X=a, (p(X,Y); q(X,Y)), !, Y=c).

Quote:
remember that once Dr. David Warren mentioned such
an optimization at Stony Brook for anonymous variables,
but that it wouldn't be appropriate because Prolog has
an operational semantics that doesn't fit this
optimization (think of the repeat predicate).

When p has no side effects, we could replace
the following:

?- X^p(X)

by:

?- \+ \+ p(X).

But when p has some side effects, on redo the second
variant will not continue doing the side effects,
whereas the first variant would do.

Bye
 
fodor...
Posted: Sun Sep 05, 2010 1:41 pm
 
On Sep 4, 5:47 pm, Jan Burse <janbu... at (no spam) fastmail.fm> wrote:
Quote:
Hi

fodor schrieb:

Now the second optimization: automatic cut:
:- ..., X=a, X^(p(X,Y);q(X,Y)), ...
if p(X,Y) succeeds, we don't have to come back to check for q(X,Y) or
to look for both p and q to get all Y.

The way that I see it, it should have a cut for X bound:
  ... ((X^(p(X,Y);q(X,Y))),!).

Well be careful with the ax. Hopefully I have
understood you correctly. Here is an example
where this transformation would not work:

     p(a,b).
     q(a,c).

     ?- X^(X=a, (p(X,Y); q(X,Y)), Y=c).

The above query is not the same as:

     ?- X^(X=a, (p(X,Y); q(X,Y)), !, Y=c).

Hi Jan,
No, in this case the cut would be at the end of the second part of the
expression.

?- X^(X=a, ( (p(X,Y); q(X,Y)), Y=c, !) ).

By this point, X is bound and there is no other variable that one
needs from the expression.

Think of the bigger pincture: there are some queries before the
expression and some queries after the expression that can backtrack.

?- ..., X^( q(X,Y)) ), ...

You really don't care about the values of Y. After succeeding for some
X, you don't care about other Ys.

If X is bound before this call, then cut can be put without problems:
?- ..., X^( q(X,Y)), ! ), ...

If X is not bound before this call, then one has to propagate inside
that Y is a "don't care variable". Lets say that the definition of q/2
is:

q(X,Y)):- p(X,Z), r(Z,Y).

Y was propagated inside as a don't care variable, Z is bound by the
time we reach the call for r(Z,Y), so this call can be executed as
"( r(Z,Y), ! )"

Paul

Quote:
 > remember that once Dr. David Warren mentioned such
 > an optimization at Stony Brook for anonymous variables,
 > but that it wouldn't be appropriate because Prolog has
 > an operational semantics that doesn't fit this
 > optimization (think of the repeat predicate).

When p has no side effects, we could replace
the following:

     ?- X^p(X)

by:

     ?- \+ \+ p(X).

But when p has some side effects, on redo the second
variant will not continue doing the side effects,
whereas the first variant would do.



> Bye
 
fodor...
Posted: Sun Sep 05, 2010 4:43 pm
 
Quote:
Hi Jan,
No, in this case the cut would be at the end of the second part of the
expression.

?- X^(X=a, ( (p(X,Y); q(X,Y)), Y=c, !) ).

By this point, X is bound and there is no other variable that one
needs from the expression.

Think of the bigger pincture: there are some queries before the
expression and some queries after the expression that can backtrack.

?- ..., X^( q(X,Y)) ), ...

You really don't care about the values of Y. After succeeding for some
X, you don't care about other Ys.

If X is bound before this call, then cut can be put without problems:
?- ..., X^( q(X,Y)), ! ), ...

If X is not bound before this call, then one has to propagate inside
that Y is a "don't care variable". Lets say that the definition of q/2
is:

q(X,Y)):- p(X,Z), r(Z,Y).

Y was propagated inside as a don't care variable, Z is bound by the
time we reach the call for r(Z,Y), so this call can be executed as
"( r(Z,Y), ! )"

Paul

Hi,
I just realized that I was using the (^) operator for the variables
that I'm interested in, while you used it as in the set predicates
bagof/3 and setof/3 for the variables that are existentially
quantified. Anyway, please think of it as I meant it, that is, for the
variables that one wants out of the query. You can use it the other
way too. It was my mistake.

The important thing is the idea that the knowledge that some arguments
are not needed outside some subgoal can be treated inside the WAM.
This happens for projections, negation as failure (the default
negation in Prolog) and findall predicates.
The implicit (early) cut is not explicit, but inferred (dynamic)
during execution. It can also be used statically for certain call
modes.

Quote:
When p has no side effects, we could replace
the following:
?- X^p(X)
by:
?- \+ \+ p(X).

Regarding your second point, your query can definitely be replaced by
(p(_),!) since the argument is used only in this subquery and
irrelevant outside the subquery. And Yes, in this case using that
double negation does exactly this, but in WAM allocates memory for the
two calls to check the negations (it saves the return pointer even
with the last call optimization), so it's better to treat X^p(X) as
(p(_),!)).

Paul.
 
Jan Burse...
Posted: Sun Sep 05, 2010 11:17 pm
 
Jan Burse schrieb:
Quote:
Ys: Variables occuring both in head and body
Zs: Variables only occuring in body
Has an implicit (^)/2. Namely the original clause would be
equivalent to the following clause:

Head :- Ys^Body

Oops, this is wrong, should read:

Head :- Zs^Body
 
Jan Burse...
Posted: Sun Sep 05, 2010 11:21 pm
 
fodor schrieb:
Quote:
It's close to what I meant, but I meant that this change is done at
the WAM level, not explicitly. And since X is not needed outside,
there is no need to return X, so, considered statically, it should be
something like:
once_X :- X, !.

Ok, you mean once_X is a predicate name, and it does not
have any arguments, i.e. arity 0. Ok, this can also be seen
as not returning X, right. Some WAM implementations(*) will
detect that X is not used anymore later and then eliminate
also any bindings generated by X.

Bye

(*) For Jekejeke Prolog, not really WAM based, this is the
body variable elimination option.
 
Jan Burse...
Posted: Sun Sep 05, 2010 11:28 pm
 
fodor schrieb:
Quote:
Actually, I meant something a bit different:
Head{Xs,Ys} :- Body{Xs,Ys}

Xs - variables whose value we are interested on after leaving the
predicate Head
Ys - variables that we don't need after leaving the call to the
predicate Head
We don't need to consider Zs, these are local variables that will be
considered while executing Body{Xs,Ys}


Easiest implementation of hidden query variables,
would possibly work as follows. Lets assume we
have the following query:

?- T^Q

Let W1,..,Wn be the variables of Q minus the variables
of T. Just create a temporary clause:

h(W1,..,Wn) :- Q

And then invoke the query:

?- h(W1,..,Wn)

When a WAM has body variable elimination it will apply
this to the temporary clause, and here we go, we have
everything!

Bye
 
Jan Burse...
Posted: Sun Sep 05, 2010 11:30 pm
 
Jan Burse schrieb:
Quote:
Easiest implementation of hidden query variables,
would possibly work as follows. Lets assume we
have the following query:

?- T^Q

Let W1,..,Wn be the variables of Q minus the variables
of T. Just create a temporary clause:

h(W1,..,Wn) :- Q

And then invoke the query:

?- h(W1,..,Wn)

When a WAM has body variable elimination it will apply
this to the temporary clause, and here we go, we have
everything!

Bye

Maybe this could be also used to optimize setof
and bagof.

Bye
 
Jan Burse...
Posted: Mon Sep 06, 2010 12:54 am
 
Jan Burse schrieb:
Quote:
When a WAM has body variable elimination it will apply
this to the temporary clause, and here we go, we have
everything!

Well not quite so. As Paul has shown, existential
quantifier would do more, namely allow the dynamic
placement of cuts...

Interesting..

Bye
 
bart demoen...
Posted: Mon Sep 06, 2010 1:17 pm
 
On Sun, 05 Sep 2010 21:28:58 +0200, Jan Burse wrote:

# body variable elimination

[I could have reacted to any of the postings containing
"body variable elimination" - just happens to be this one]

Have you looked at the relation with Region Based Memory Management ?
[and sorry if I overlooked someone already pointing that out]

Cheers

Bart Demoen

--- news://freenews.netfront.net/ - complaints: news at (no spam) netfront.net ---
 
 
Page 2 of 2    Goto page Previous  1, 2
All times are GMT
The time now is Wed Apr 16, 2014 7:25 am