[mercury-users] Re: BOUNCE mercury-users at cs.mu.OZ.AU: Non-member submission from [Don Smith <dsmith at rsn.cirl.uoregon.edu>]

[Bart Demoen]

Don wrote:

> The problem seems to be
> that setof/3 copies terms in each solution, so each time a new solution
> is collected the entire existing graph is copied, even though the graph
> is ground and could in fact be shared.

Ah, so finally someone ran into this :-)
3 or 4 years ago, Paul Tarau and I wrote a paper on how badly Prolog
systems implement higher order predicates, including findall and
friends. One of the things being that (ground) sharing between
solutions is not kept. Unfortunately the paper isn't of any help to
Don and there is no implementation that will help him readily, except
perhaps Mercury with zero-copy setof and Boehm collector but it has
other drawbacks.

> the program calls
> setof/3 to collect solutions, each of which references the graph from
> earlier levels

Perhaps you can keep these references as variables during the setof
and instantiate them after the setof to the previous graph. Or hack a
bit in setof: at the place where the solutions are recorded, transform
the solution so that it contains something that lets you reconstruct
the graph instead of the graph itself.

In BIMprolog (no IT-Prolog), I experimented with sharing between
recorded terms (with our version of recorda which is only slightly
different from the DEC-10 one) and terms on the heap (also two or more
recorded terms could share) This was in the context of memoing. For
some programs (e.g. executing the boyer benchmark with memoing) it
payed of a lot. And it is not so hard to implement.

Bart