[m-dev.] Suggestion for a new "where" operator

[Peter Moulder]

This message tries to gather together information relevant to whether or
not the `E where G' goal G should be limited to produce no more than one
solution for variables used in E, if a `where' operator is introduced.

> > >   - If the inserted goals can fail or produce multiple solutions, then
> > >     EXPR = EXPR can fail.  (IIRC, one reason that Mercury doesn't
> > >     support multi/nondet functions was to avoid cases where EXPR = EXPR
> > >     fails.)

The above formulation was too loose re multiple solutions.

`q((X where p(X)), (X where p(X)))' has the same declarative semantics
as `some[V] (V = (X where p(X)), q(V, V))' regardless of the number of
elements in {X : p(X)}.

   p(X), p(X), q(X, X)              (duplicate-where version)

   some[V] (p(X), V = X, q(V, V))   (single-where version)

(The difference from multi functions is that each function invocation
introduces a new fresh variable, whereas the goals of identical `where'
expressions occurring in a common scope act on identical variable
tuples.)

[Interestingly, the two versions of the goal can have different
 determinisms (or even produce a mode error in the duplicate-where
 version) if the first p call changes the instantiatedness of X.  E.g. if
 (p(out) is det) is chosen for the initial p(X) call (i.e. p(free >>
 ground) is det), then the second p(X) call in the duplicate-where
 version can resolve to (p(in) is semidet), and the compiler may
 (over-cautiously) complain that the goal can fail.]

A consequence of the above q(V, V) equivalence is that
`(X where p(X)) = (X where p(X))' will fail if and only if a p call
fails.  (Ignoring NaN bugs.)  It does not depend on whether or not
p(out) produces multiple solutions.


Introduction of performance problems ?  If we follow fjh's suggestion of
allowing the `where' expression to be nondeterministic if some of the
non-local variables other than those in the result have output modes,
then the question of whether or not to allow nondeterminism in other
cases affects only the frequency of such problems appearing in code
rather than whether or not there are new possibilities of performance
problems that programmers must look for.

Presumably the effect of the proposed determinism restriction on user
code would be that the user would insert extra goals (and perhaps also
transform if-then-else expressions) for themselves, in code that the
user would otherwise prefer to use `where' expressions.  There would be
little difference in the performance characteristics.  Some differences:

  - Forcing the programmer to avoid `where' expressions may make it
    easier for the programmer to see the "default ordering", i.e. the
    ordering of calls after syntactic transformations and before mode
    reordering.  And hence to guess the ordering after mode reordering,
    and hence to guess the ordering after optimizations.

    "may make it easier": e.g. because depth-first left-to-right
    ordering is harder to see than the syntactic left-to-right when the
    `where' goals are separated out.  E.g.2 because the procedure calls 
    in the separated-out form will typically appear at the start of a
    line, so are easier for the programmer to see at a glance (i.e.
    harder to go unnoticed).

    Note that these disadvantages of the proposed-to-be-disallowed
    multidet `where' goals are also disadvantages of already-allowed
    functions with multiple solutions of function arguments and
    proposed-allowed `where' goals that have multiple solutions in
    variables not appearing in the E expression.  However, use of
    functions in modes where arguments are outputs are rare, and it may
    be that `where' goals with multiple solutions for variables not used
    in E are also rare.


Another suggested reason for disallowing `where' goals with multiple
solutions in variables in the corresponding E is so that `where'
expressions "behave more like function calls".  Can someone else please
try to elucidate some benefits of this, or at least voice a gut feeling
that this is desirable?  For me, it does have some intuitive appeal, but
OTOH I wonder whether the "p(f, f)" difference from functions noted
above means that this isn't so important for `where' expressions.

pjm.

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------