[m-users.] When is nondeterminism appropriate?

[Zoltan Somogyi]

2021-02-15 07:32 GMT+11:00 "Philip White" <philip at pswhite.org>:
> Hello,
> I'm confused when it is a good idea to make functions and predicates
> that are anything but deterministic. Whenever I write a function that
> could potentially not have any solutions, often that failure has the possibility that it can trickle up to the top of the application and
> need to be displayed to the user. Since I want to give the best
> possible error message, I want to store a message about the cause of
> the error with all the context about why it was caused, instead of
> printing a generic "Error". To do this, I often use a result type:
> 
> :- type result ---> ok(T) ; error(string).
> 
> "functions that can fail" (either because of user error or something
> else) seems like the perfect time to use semidet, but if I
> want to have good error messages, then semidet will not help me, and I
> might as well try to make my function deterministic.

There are cases in which one can give good error messages without knowing
the details of a failure. For example, if you have a query "list all the ways
you can take a train from London to New York", you don't need to know
exactly what part of the train network that query explored to give the
error message "you can't get to New York from London using only trains".
And of course there are many computations that can fail whose failure
does not need to be reported to users at all. How frequent these are
of course depends on your domain.

> 1. Can someone give a real example of when nondeterminism has been
> useful?

There are some, but not many. For example, in the Mercury compiler,
only about one percent of all predicates can succeed more than once,
and a large fraction of those predicates are library predicates that
have no nondeterminism themselves, and are only nondeterministic
because they take user-supplied nondeterministic higher order values
as arguments.

The usual kind of nondet code in the compiler computes the set
of entities that satisfies a given property using generate-and-test:
a call to a generator predicate, which succeeds once for each
entity in a class of entities, and a semidet test that succeeds
only if the entity has the required property. One could also compute
the same results using det code that iterates over the class
and inserts each entity that has the property into a set.
The generate-and-test approach usually yields smaller and cleaner
code, since it does not need to deal with managing a collection,
since it can leave that to the library's solutions predicate.
The price for that is that generate-and-test is usually slower.
However, in many cases, the structure of the problem guarantees
that the search space will be so small that any speed difference
will be too small to matter.

> 2. Is there a way to track "functions that can fail" while also
> maintaining info about that failure?

There is no automatic way, because what info you want to maintain
about failures depends far too much on the task at hand. The standard
way to do it by hand is to use some variation on your result type above.

> The language reference manual explains technically how determinism
> modes work, but it doesn't give much guidance on how to pick the
> appropriate determinism.

The Mercury crash course, which is reachable from the documentation
section of mercurylang.org, has some material you may find useful.

Zoltan.