Prolog - how to rename variables?

Author

how to rename variables?

Giovanni Gherdovich

2007-08-23, 10:10 pm

Hello.

I wonder if I can find in Prolog a build-in predicate
that allow me to rename all the variables in a list
of terms in order to make these terms to don't
share variables.

Something that behaves like this:

?- rename([X+Y, f(X,g(X))], OutputList).

OutputList = [X1+X2, f(X3,g(X3))]

I know the predicate gensym, that associates
an unique atom to every variable of a list,
but my problem is slightly different...

Thankyou.
Giovanni

Bart Demoen

2007-08-23, 10:10 pm

Giovanni Gherdovich wrote:
> Hello.
>
> I wonder if I can find in Prolog a build-in predicate
> that allow me to rename all the variables in a list
> of terms in order to make these terms to don't
> share variables.
>
> Something that behaves like this:
>
> ?- rename([X+Y, f(X,g(X))], OutputList).
>
> OutputList = [X1+X2, f(X3,g(X3))]

Try copy_term/2.

Cheers

Bart Demoen

Giovanni Gherdovich

2007-08-25, 8:05 am

Chip Eastham

2007-08-25, 7:08 pm

On Aug 25, 5:43 am, Giovanni Gherdovich
<gherdov...@students.math.unifi.it> wrote:
> Dear Mr. Demoen,
>
>
> Yes, this is the right predicate;
> thankyou.
>
> | ?- copy_term(X+Y, OutputTerm).
> |
> | X = _G180
> | Y = _G181
> | OutputTerm = _G272+_G273 ;
> |
> | No
> | ?- copy_term(f(X,X), OutputTerm).
> |
> | X = _G180
> | OutputTerm = f(_G257, _G257) ;
> |
> | No
>
> Regards,
> Giovanni

Hi, Giovanni:

I believe you have noticed that, to get the result
described in your original post, where the X in
the term X+Y first listed is not bound to the same
new variable as the X in the term f(X,X), you will
need to apply copy_term/2 to each entry in the list
of terms.

| ?- copy_term([X+Y,f(X,g(X))],OutTerm).
|
| X = _G187
| Y = _G188
| OutTerm = [_G300+_G301, f(_G300, g(_G300))] ;

As the above illustrates, passing the entire list
at once to copy_term creates a coherent mapping of
the variables, X going from _G187 to _G300 in all
appearances, while your example had the X in the
first term coming "unglued" from the X's in the
second term of the list.

regards, chip

Markus Triska

2007-08-25, 7:08 pm

Chip Eastham <hardmath@gmail.com> writes:

> you will need to apply copy_term/2 to each entry in the list

You can also use:

%?- Ls = [X+Y, f(X,g(X))], findall(C, member(C, Ls), Cs).
%@ Cs = [_G317+_G318, f(_G306, g(_G306))]

And copy_term(T, C) can also be obtained by: findall(T, T==T, [C]).

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

Markus Triska

2007-08-26, 7:13 pm

Jan Wielemaker <jan@nospam.ct.xs4all.nl> writes:

> True, but copy_term/2 is more efficient and the detailed semantics

Indeed; however, the "term copying" property of findall is worth
knowing since it can be used to define the entire evaluation strategy
of pure Prolog in a single line of semi-deterministic Prolog code:

step([A|As0], As) :- findall(Gs-G, (A=[G0|Rest]-G,ld(G0,Gs,Rest)), As, As0).

It assumes clauses in the form of list differences, like:

ld(natnum(0), Gs, Gs).
ld(natnum(s(X)), [natnum(X)|Gs], Gs).

The interface predicates for the meta-interpreter could be:

mi(G0) :- mi([[G0]-G0], G0).

mi([[]-G|_], G).
mi(As0, G) :- step(As0, As1), mi(As1, G).

Example query:

%?- mi(natnum(X)).
%@ X = 0 ;
%@ X = s(0) ;
%@ X = s(s(0)) ;
%@ X = s(s(s(0))) a
%@ Yes

Luckily, the CVS version of SWI Prolog already includes findall/4, the
list difference version of findall/3. Otherwise, the meta-interpreter
would - wastefully - have taken 2 lines. :-)

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

bart demoen

2007-08-27, 8:04 pm

On Sun, 26 Aug 2007 23:34:06 +0200, Markus Triska wrote:

> Indeed; however, the "term copying" property of findall is worth
> knowing since it can be used to define the entire evaluation strategy
> of pure Prolog in a single line of semi-deterministic Prolog code:
>
> step([A|As0], As) :- findall(Gs-G, (A=[G0|Rest]-G,ld(G0,Gs,Rest)), As, As0).

I had never considered the question
what would be the worst reason why I would like to know about
the copying semantics of findall/3 ?

I now know the answer - I am so happy !

Reminds a bit of 42.

Bart Demoen

Markus Triska

2007-08-27, 8:04 pm

bart demoen <bmd@cs.kuleuven.be> writes:

> I had never considered the question
> what would be the worst reason why I would like to know about
> the copying semantics of findall/3 ?
>
> I now know the answer - I am so happy !

Nice to hear - and what would it be? (We already covered findall/*4*.)

bart demoen

2007-08-27, 8:04 pm

On Mon, 27 Aug 2007 22:55:46 +0200, Markus Triska wrote:

> bart demoen <bmd@cs.kuleuven.be> writes:
>
[color=darkred]
>
> Nice to hear - and what would it be? (We already covered findall/*4*.)

Maybe you need to do some homework: the copying semantics of
findall/x is the same for x = 3 and 4

Cheers

Bart Demoen

ps. findall/4 might impress people as the most recent version of sliced
bread (and I surely agree that it is useful, very useful indeed); it was
in BIM-Prolog since ... always; I should consult my old manuals, but the
MasterProlog version of BIM-Prolog of 15-Aug-1999 (still running here in
Leuven, and used on a daily basis) has findall/4; also SICStus has it, and
Yap and B-Prolog (with the last two args switched) - XSB, ECLiPSe and
GNU-Prolog seem not to know about it, but I might have missed their local
variant of it - it isn't ISO after all

cheers once more :-)

Jan Wielemaker

2007-08-28, 5:26 am

On 2007-08-27, bart demoen <bmd@cs.kuleuven.be> wrote:
> On Mon, 27 Aug 2007 22:55:46 +0200, Markus Triska wrote:
>
>
>
> Maybe you need to do some homework: the copying semantics of
> findall/x is the same for x = 3 and 4
>
> Cheers
>
> Bart Demoen
>
> ps. findall/4 might impress people as the most recent version of sliced
> bread (and I surely agree that it is useful, very useful indeed); it was
> in BIM-Prolog since ... always; I should consult my old manuals, but the
> MasterProlog version of BIM-Prolog of 15-Aug-1999 (still running here in
> Leuven, and used on a daily basis) has findall/4; also SICStus has it, and
> Yap and B-Prolog (with the last two args switched) - XSB, ECLiPSe and
> GNU-Prolog seem not to know about it, but I might have missed their local
> variant of it - it isn't ISO after all

I added findall/4 on request and value compatibility a lot, but I still
wonder what is wrong with:

...
findall(Gen, Goal, Sols),
append(Sols, Tail, Result),
...

Efficiencywise findall/3 is a joke anyway, and the append doesn't make
it significantly worse. I consider findall/3 as a need-to-have, but
otherwise as an undesirable beast like the cut. Its the least unelegant
way to save data over backtracking, but that is about it. Think of
examples like

count_solutions(Goal, Count) :-
findall(x, Goal, Xs),
length(Xs, Count).

Who will consider creating a list of Xs just to count solutions? Even if
we are looking for distinct solutions, sensible progammers make a table
and add only new solutions to this table. They maintain the size of the
table, request it at the end and drop the table. Using setof/3 or
findall/3+sort/2 for this task makes more sense than the above counting
example, but it is still a second-best solution.

As said, besides these considerations semantics get unclear if we have
mutable terms or constraints in the picture.

Cheers --- Jan

Adpoencehaup

2007-08-29, 2:45 am

http://www.reyrewh.com/WatchMovie?clip=726648

Markus Triska

2007-08-30, 8:09 pm

Jan Wielemaker <jan@nospam.ct.xs4all.nl> writes:

> Efficiencywise findall/3 is a joke anyway [...] Its the least
> unelegant way to save data over backtracking, but that is about it.

On the plus side, I'd add quick memory reclamation in some cases, also
for completely deterministic programs like:

make_garbage(L) :- length(Ls, 1000), length(Ls, L). % artificial

solution1(0, N, N) :- !.
solution1(S, N0, N) :-
make_garbage(L), N1 is N0 + L, S1 is S - 1, solution1(S1, N1, N).

solution2(0, N, N) :- !.
solution2(S, N0, N) :-
findall(G, make_garbage(G), [L]), % sole difference
N1 is N0 + L, S1 is S - 1, solution2(S1, N1, N).

%?- time(solution1(20000, 0, N)).
%@ % 120,001 inferences, 1.16 CPU in 1.41 seconds (82% CPU, 103449 Lips)
%@ N = 20000000 a

%?- time(solution2(20000, 0, N)).
%@ % 340,001 inferences, 0.64 CPU in 0.65 seconds (99% CPU, 531252 Lips)
%@ N = 20000000 ;

solution2/3 uses findall/3 and thus a failure-driven loop to obtain
the result of make_garbage/1, taming garbage collection in this case.
The tabled approach you mentioned has of course the same advantage.

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

bart demoen

2007-08-30, 8:09 pm

On Tue, 28 Aug 2007 08:26:00 +0000, Jan Wielemaker wrote:

> I added findall/4 on request and value compatibility a lot, but I still
> wonder what is wrong with:
>
> ...
> findall(Gen, Goal, Sols),
> append(Sols, Tail, Result),
> ...

What is wrong with implementing findall/4 and then defining

findall(Template,Goal,List) :- findall(Template,Goal,List,[]).
?
That's how I always implemented findall/3.
It shows that the basic thing is findall/4, so why not give it to
the user.

> Efficiencywise findall/3 is a joke anyway,

It is only a joke to those implementions that do not take it seriously.

> otherwise as an undesirable beast like the cut. Its the least unelegant
> way to save data over backtracking, but that is about it.

To me, findall/* is the most helpful way for rapid prototyping: getting
quickly a program that is correct and often works even for large inputs.

On top of that, it often does not increase the runtime complexity of the
program, but makes it so much clearer how to prove it correct as compared
to a more involved technique.

Moreover, compare it to list comprehensions in (say) Haskell: extremely
useful in the specification of a solution, especially when one doesn't
know yet the optimal algorithm. Haskell takes list comprehensions
seriously - why don't we ?

> Think of examples like
>
> count_solutions(Goal, Count) :-
> findall(x, Goal, Xs),
> length(Xs, Count).

It is easy to give ridiculing examples of the usage of findall. But the
real problem is that Prolog only provides the aggregate "all solutions".
Other useful aggregates (sum, count, ...) are left to the programmer to
implement using either findall, or some other even lower-level
feature like assert/retract or other non-backtrackable update.

I concur totally with Markus on the garbage collection side: I think
it was Paul Tarau who used to call findall/3 "the poor man's garbage
collector".

Nevertheless, gc consideration is something LP programmers would like
not to be bothered with.

The only way out of this is ... more research on how to compile
specifications using aggregates (and a wider variety of them as well)
in the context of an LP language (like Prolog).

> As said, besides these considerations semantics get unclear if we have
> mutable terms or constraints in the picture.

That is merely a question of specification of the semantics: it seems we
are not ready for it yet, but that doesn't mean that we should "throw away
the baby with the bathing water" (as we say in flemmish :-)

Cheers

Bart Demoen

Jan Wielemaker

2007-08-31, 5:14 am

On 2007-08-30, bart demoen <bmd@cs.kuleuven.be> wrote:
> On Tue, 28 Aug 2007 08:26:00 +0000, Jan Wielemaker wrote:
>
>
> What is wrong with implementing findall/4 and then defining
>
> findall(Template,Goal,List) :- findall(Template,Goal,List,[]).

Of course if you want both than this is the way to go (and how it works
in the current CVS version of SWI-Prolog). The question is whether or
not to include findall/4. I have, motivated by compatibility and on
request. Otherwise I probably wouldn't have. In all the
hundred-thousands of lines of Prolog I've only needed it a few times.
While there are many predicates producing a list for which it is much
more useful. Think of atom_codes/2 and friends. An atom_codes(+Atom,
Codes, Tail) is very handy in DCGs and it is likely to have much bigger
impact on relevant programs.

> That's how I always implemented findall/3.
> It shows that the basic thing is findall/4, so why not give it to
> the user.
>
>
> It is only a joke to those implementions that do not take it seriously.

I was surprised by Markus example. Ok, this is a pretty bad one,
SWI-Prolog findall/3 is pretty fast (as you probably know) and the CVS
version has a new implementation that is almost twice as fast. According
to the profiler, the findall overhead of Markus' program is about 8%.
SWI-Prolog GC is pretty slow and is responsible for 48% of the solution1
program.

>
> To me, findall/* is the most helpful way for rapid prototyping: getting
> quickly a program that is correct and often works even for large inputs.

I'd be more in favour of extending maplist-like schemas. They can often
match in compactness with findall, but without the copy semantics
problems. Note that I'm particulary aiming at replacing things like
this:

findall(X, (member(E, List), something(E, X)), Xs)

>
> It is easy to give ridiculing examples of the usage of findall. But the
> real problem is that Prolog only provides the aggregate "all solutions".
> Other useful aggregates (sum, count, ...) are left to the programmer to
> implement using either findall, or some other even lower-level
> feature like assert/retract or other non-backtrackable update.

Doing some agregate operation over all solutions is quite common. Using
findall is generally limits the size of the data that can be processed
due to the intermediate list.

> I concur totally with Markus on the garbage collection side: I think
> it was Paul Tarau who used to call findall/3 "the poor man's garbage
> collector".
>
> Nevertheless, gc consideration is something LP programmers would like
> not to be bothered with.

Just of of curiosity, could you repeat these timings on a few `fast'
Prolog systems? It appears you have many installed :-)

> The only way out of this is ... more research on how to compile
> specifications using aggregates (and a wider variety of them as well)
> in the context of an LP language (like Prolog).

Agree.

>
> That is merely a question of specification of the semantics: it seems we
> are not ready for it yet, but that doesn't mean that we should "throw away
> the baby with the bathing water" (as we say in flemmish :-)

Specification may help, provided it is possible to come up with a nice
and clean specification that can be implemented efficiently on most
Prolog architectures. Considering recent discussions on mutable terms
and attributed variables doesn't make me hopeful.

Of course, I'm just teasing a bit :-) I'll use findall, even findall/4
if it helps winning the Prolog contest :-)

Cheers --- Jan

Bart Demoen

2007-08-31, 8:56 am

Jan Wielemaker wrote:

> I was surprised by Markus example. Ok, this is a pretty bad one,
> SWI-Prolog findall/3 is pretty fast (as you probably know) and the CVS
> version has a new implementation that is almost twice as fast. According
> to the profiler, the findall overhead of Markus' program is about 8%.
> SWI-Prolog GC is pretty slow and is responsible for 48% of the solution1
> program.
....
>
> Just of of curiosity, could you repeat these timings on a few `fast'
> Prolog systems? It appears you have many installed :-)

I ran into some strange looking results, until I realised that
one should probably subtract the time make_garbage takes before making
any conclusions; the reason is that SWI implements length/2 in C,
while not all other systems do so.

So what I report is
((time for solution1)-(time spend in make_garbage))
divided by
((time for solution2)-(time spend in make_garbage))

This should get an idea of how much slower relying on gc is than using
findall+instant reclaiming. Those ratios should not be used to rank
systems on the gc scale, neither on the findall scale.

I then got the following results:

SWI: 11
SICStus: 0.96
hProlog: 1.8
Yap: 2.3
B-Prolog: 1.2
ECLiPSe: 9

AFAIK, SWI, SICStus and Yap use basically the same algo for gc: Morris.
hProlog uses copying (and this benchmark favours a copying gc because
there is always very little garbage)
B-Prolog collects only the top segment, but there is basically only
one segment in this program.
Don't know what ECLiPSe does for gc.
But it doesn't look like the underlying gc algo has the biggest impact on
the figures.

Cheers

Bart Demoen

Joachim Schimpf

2007-09-03, 7:06 pm

Bart Demoen wrote:
> Jan Wielemaker wrote:
>
>
> ...
>
>
> I ran into some strange looking results, until I realised that
> one should probably subtract the time make_garbage takes before making
> any conclusions; the reason is that SWI implements length/2 in C,
> while not all other systems do so.
>
> So what I report is
> ((time for solution1)-(time spend in make_garbage))
> divided by
> ((time for solution2)-(time spend in make_garbage))

How do you measure the time in make_garbage reliably,
in particular excluding gc?

>
> This should get an idea of how much slower relying on gc is than using
> findall+instant reclaiming. Those ratios should not be used to rank
> systems on the gc scale, neither on the findall scale.
>
> I then got the following results:
>
> SWI: 11
> SICStus: 0.96
> hProlog: 1.8
> Yap: 2.3
> B-Prolog: 1.2
> ECLiPSe: 9

I don't think you are measuring anything interesting here at all.
You compare something that is essentially constant (one failure
plus a constant size copy for the findall version) with something
that is non-constant (the size of copied/scanned stack in garbage
collection), making the wide range of results unsurprising.

For a mark&compact collector, the gc parameters (size of stack
at collection time) will be the main influence, or even the number
of times you repeat the benchmark (N).

For a copying collector, the length of the list in make_garbage
will be the main factor (since on average half a list will need
copying at gc time).

I haven't done measurements, but I'd expect that by varying
list length and N, you can get pretty much any factor.

-- Joachim

bart demoen

2007-09-03, 7:06 pm

On Mon, 03 Sep 2007 20:25:03 +0100, Joachim Schimpf wrote:

> How do you measure the time in make_garbage reliably,
> in particular excluding gc?

I tried to make minimal changes to solution1 by Markus,
but so that gc would not be triggered, so I hardly had
any other choice than calling make_garbage, fail in a loop.
Here it is

solution3(0, N, N) :- !.
solution3(S, N0, N) :-
make_garbage(_), fail
;
N1 is N0 + 1000, S1 is S - 1,
solution3(S1, N1, N).

Whether it is reliable ... maybe it depends on what you call
reliable: in my experience, this is usually pretty good - but
you have to check whether gc is called, and if so, make the
heap larger at startup time.

I know about memory footprint, cache size etc, but if you have a more
reliable method, please tell us. If your point is that it is
scientifically impossible to measure reliably anything at all, I agree.

>
>
> I don't think you are measuring anything interesting here at all.
> You compare something that is essentially constant (one failure
> plus a constant size copy for the findall version) with something
> that is non-constant (the size of copied/scanned stack in garbage
> collection), making the wide range of results unsurprising.

I only partly agree with you here. It surely is true that the ratio I
showed cannot make a statement about complexity, but it does about
relative performance for one point in the space of N and size of list.
It seems that you would have been more happy if I had included the size of
the heap for each system, or had the measurements done with exactly the
same heape size (to start off with) for each system, and on top of that
with a wide range of (N,size) - I wish I had more time.

> I haven't done measurements, but I'd expect that by varying
> list length and N, you can get pretty much any factor.

I will leave the burden of proof for this statement to you :-)

Since the complexities differ for the different operations at play,
you are probably right: I expect that while one can achieve "pretty much
any factor", one will notice that some systems have consistently a (much)
lower factor than others; btw, I think that for systems with a copying gc
(like hProlog) the factor will be close to constant, because findall and
gc both use copying and for this benchmark, the other stacks are contant
size.

I haven't mentioned the absolute figures (timings for each and every part
of what I measured) but they are very revealing; however they would be
subject to the same critisism that only one point in the space of (N,size)
is measured, so I will refrain from showing them.

Cheers

Bart Demoen

Joachim Schimpf

2007-09-04, 7:09 pm

bart demoen wrote:
> ...
>
>
> I only partly agree with you here. It surely is true that the ratio I
> showed cannot make a statement about complexity, but it does about
> relative performance for one point in the space of N and size of list.

But the relative performance of what? We are dividing A/B, where

A = something that might (or might not, as I suspect in the case
of the Sicstus result) contain some garbage collection time

B = something that is very close to zero, making the results
very sensitive to timer resolution

I've tried, and with a single system (ECLiPSe) I can in fact get
results between just over 1 and infinity, just with different stack
sizes resp. gc triggering threshold.

Therefore I'd say this program is really quite useless as a benchmark
(and I guess Markus didn't intend it to be taken that seriously).

> It seems that you would have been more happy if I had included the size of
> the heap for each system, or had the measurements done with exactly the
> same heape size (to start off with) for each system, and on top of that
> with a wide range of (N,size) - I wish I had more time.

No, I wouldn't know what to to with these numbers. I think time
would be better spent designing benchmarks whose results have
a more straightforward interpretation.

-- Joachim

bart demoen

2007-09-04, 7:09 pm

On Tue, 04 Sep 2007 15:20:07 +0100, Joachim Schimpf wrote:

>
> But the relative performance of what?

I think the relative performance of relying on forward execution+gc versus
a failure driven loop which does not need to save much persistent data
over backtracking.

> We are dividing A/B, where
>
> A = something that might (or might not, as I suspect in the case
> of the Sicstus result) contain some garbage collection time

Of course there is gc - that's the whole point !
But there is nothing like a refuted suspicion :-)

SICStus:
0.330 sec. for 140 garbage collections which collected 159350296 bytes
0.330 secs is 28% of the total time.

ECLiPSe:
gc_number: 88
gc_collected: 352691704.0 bytes
gc_time: 0.47 seconds
Those 0.47 secs were 31% of total time.

So maybe now the figures start to take on some meaning ? Even if (*)

> B = something that is very close to zero, making the results
> very sensitive to timer resolution

B is (unfortunately) not that close to zero: even though the copied
template is small, the overhead of findall is often large (compared to
doing forward computation+gc). The figures show that it is relatively
larger for SICStus than for ECLiPSe - but it would take closer inspection
of the absolute timings to say which system perform "better".

> I've tried, and with a single system (ECLiPSe) I can in fact get
> results between just over 1 and infinity, just with different stack
> sizes resp. gc triggering threshold.

So you confirmed what we expected: one can get pretty much any ratio.
But that was not the original point: the point of making the ratios iss
that for each combination of stack size. and N and list size, one should
look at the ratios of ALL the systems. The point is not to make a
statement about whether X is good at something or not, but whether in X it
pays off better to rely on gc than on findall (for some particual piece of
program) than in Y.

> Therefore I'd say this program is really quite useless as a benchmark
> (and I guess Markus didn't intend it to be taken that seriously).

Nobody was suggesting it to be used as a benchmark in the traditional
sense like in "let's find out something about performance of individual
systems". The issue started with "findall can be used as a replacement of
gc". This is more true in some systems than in others. That's what the
ratio shows to me.

>
> No, I wouldn't know what to to with these numbers.

I wouldn't even think about trying to refute that.
OTOH, I myself do know what these numbers mean to me.

> I think time
> would be better spent designing benchmarks whose results have
> a more straightforward interpretation.

True. Unfortunately, any time a new benchmark is designed, or proposed,
it is subject to critisism of the same kind as you had on my ratios.
Fair enough: benchmarking is a though business.

BTW, I am very curious: what is the most recent benchmark that the
community has ackowledged as meaningful ? Anyone knows ?

Cheers

Bart Demoen

Joachim Schimpf

2007-09-05, 8:05 am

bart demoen wrote:
> On Tue, 04 Sep 2007 15:20:07 +0100, Joachim Schimpf wrote:
>
>
> I think the relative performance of relying on forward execution+gc versus
> a failure driven loop which does not need to save much persistent data
> over backtracking.
>
>
>
> Of course there is gc - that's the whole point !

Not necessarily - which was my whole point.
If N is small enough, or the stacks large enough and
the gc triggers late enough, you won't have any gc
in your measurement. And then the "gc" version has
of course a good chance of being faster than findall :-)

-- Joachim

Bart Demoen

2007-09-05, 8:05 am

Joachim Schimpf wrote:

>
>
> Not necessarily - which was my whole point.

It was the whole point of Markus' program: findall
can be a cheap alternative to gc. Unless I misunderstood
Markus' intention totally.

Cheers

Bart Demoen

Sponsored Links