[m-users.] When is nondeterminism appropriate?

[Philip White]

On Mon, 15 Feb 2021 10:30:53 +1100 (AEDT)
"Zoltan Somogyi" <zoltan.somogyi at runbox.com> wrote: 
> 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.

I think the reason why this error message is acceptable is that the
details of the error message would probably be confusing and unhelpful
("here is a list of the 1 million paths I tried"). However, I'm of the
mind that if there is useful context for an error, you should preserve
it for the user. ("file not found" isn't a great error, the program
should say which file was expected, but not found).

Anyway, this is rather beside the point of my question, so it's not
worth laboring over.

> > 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.

The comparison between "operating on collections" vs nondeterminism
makes sense. My internet searching seems to confirm this as well.

> > 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.

Yeah, this sounds right. Maybe I'm just wishing that Mercury had some
form of do-notation or syntactic convenience for monads and
applicatives. I've been brainstorming about how do-notation would even
work in a logic programming language, but I'm running into a wall. I
haven't been able to find any literature on the subject either.

> > 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.

Thanks for the reference. I've seen that before, but it's gotten
more comprehensive than it was when I last looked at it.

- Philip