[mercury-users] Re: first_soluition/1, etc

[Lee Naish]

In message <199710301928.IAA28147 at lucy.cs.waikato.ac.nz>you write:
>OK, here's a description of why I wanted choice predicates.
>In a planning application, I needed to collect the list of all applicable 
>action instances (actions whose preconditions are satisfied) and then the
>list of all facts enabled by some applicable action instance.  These procedures
>were inside a nondeterministic loop which selects subsets of relevant actions
>to consider, and inside another, outer, iterative-deepening loop.  (One
>could imagine yet another loop which examines the answers returned by 
>the inner loops and evaluates them or finds the groups of 5 solutions and
>then does something else.)
>
>At first I tried using solutions/2 to do both of these aggregate collection
>operations.  But the running time was horrendous, because the solution terms
>contain pointers to earlier parts of the graph, and so the list was sorted
>more than it needed to be.

If the major problem was the time spent sorting then you might be able
to return something a bit different out of the all solutions predicate
(a different, smaller, representation of the large term) then substitute
in the representation you really want after collecting the solutions.  This
is sometimes very desirable in Prolog to avoid copying large terms with all
solutions predicates (and the same applies to Mercury to a lesser extent,
depending on what GC mode you use).  There was some discussion in
comp.lang.prolog recently about this.

>Can we use a nonstandard equality theory and say that any permutation of the
>list of solutions is the same as any other?  Maybe, but it really depends on 
>my algorithm:  from the point of view of my algorithm, any order is OK. 

I think for some things this is the best solution.  However, typically you
want to process the elements one at a time and this also involves a choice
at each stage (unless we have enough general purpose higoer order predicates
to apply the appropriate operations to the members of the collection).  In
any case there should be some guarantee that the operations we perform are
in fact going to return the same answer independent of the order.  I believe
this should ideally be made explicit in the form of assertions in the code.
Expressing it can be rather tricky in cases like yours where the outer level
is nondeterministic.  You have to say something like: This nondeterministic
choice I'm making in this subcomputation won't affect the set of solutions
at this upper level of the computation.  The kind of assertions I have
designed only work at a local level and I have not come up with a nice way
to do these more global assertions.

>Fergus wrote:
>>`first_solution' is not referentially transparent;

>> add an extra, distinguishing tag argument (e.g., a string representing the 
>> static syntactic call with arguments) to calls to choice predicates.

>But Lee says:
>>It simply doesn't work.  To get referential transparency you need to be
>>able to replace equals by equals.  This is not replacing syntactic
>>equals by equals

>Well, in Prolog (and Mercury, as far as I know), identity of first-order terms
>_is_ syntactic.

True, but the Mercury all solutions predicates use higher order terms,
where equality is not simply syntactic.  Eg, the function add(2) equals
the function subtract(-2) (add some lambdas/preds etc to make this
legal Mercury).  You can make first_solution declarative in Prolog or
Trilogy because it doesn't use these abstract higher order things.

	lee