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

[Lee Naish]

>In mercury-users at cs.mu.OZ.AU, Don writes:
>> 
>> I am writing a Prolog application which builds a graph structure level
>> by level.  To extend the (ground) graph to a new level the program calls
>> setof/3 to collect solutions, each of which references the graph from
>> earlier levels.  When I run the program under sicstus 2.1, eclipse 3.5.2,
>> or BinProlog 5.0, it uses way too much memory.   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.
>> 
>> I need a Prolog which will be smart enough to (let me specify that it's OK
>> to) copy only the new part of each solution.   Do you think Mercury might
>> do this, thanks to its use of mode info?   Will any standard Prologs let 
>> me do this?

NU-Prolog solutions/3 sometimes does better than setof/3 because it has
more information about groundness.  However, NU-Prolog has no garbage
collector.

It might be best to rewrite your code so that the terms collected in
setof don't contain the existing graph (they could perhaps contain some
small dummy term which represents the large graph).  You can then write
some ordinary Prolog code (ie, not using setof) which takes the terms
produced by setof and constructs the complete graph(s) - this code will
not copy the existing graph.

An example of this kind of thing is the poorly coded heuristic search
algorithm in the first edition of Bratko's AI in Prolog book.  The code
needed to find the successors of a node in a graph and construct paths
back to the root for each successor (the path from the node was given).
Bratko did everything inside findall, which resulted in all the paths
being copies.  Below is the code:

%       % find list of successors (inefficient version)
%pss(p(_F, G, N.P), PSL) :-
%       findall(p(F1, G1, N1.N.P),
%               ( s(N, N1, Cost),
%                 G1 is G + Cost,
%                 heur(N1, H1),
%                 F1 is G1 + H1
%               ), PSL).

        % find list of successors (efficient version)
        % does not duplicate paths
        % eg, pss(p(_,G,N.P),
        %       [p(F1,G1,N1.N.P,
        %        p(F2,G2,N2.N.P,
        %        p(F3,G3,N3.N.P, ...])
        % where N1,N2,N3,... are the
        % successors of N
pss(p(_F, G, Node.Path), PSL) :-
        findall(sn(F1, G1, SNode),
                ( s(Node, SNode, Cost),
                  G1 is G + Cost,
                  heur(SNode, H1),
                  F1 is G1 + H1
                ),
                SNodes),
        cons_paths(SNodes, Node.Path, PSL).

        % For each successor node, generate a new path (with the node
        % as the head) and return the list of p/3 structures
        % with these paths.
        % (like cons_each in breadth first)
cons_paths([], _, []).
cons_paths(sn(F, G, SNode).SNodes, Path, p(F, G, SNode.Path).PSL) :-
        cons_paths(SNodes, Path, PSL).


Another possibility is to reimplement setof (not too hard).

	lee