## Sunday, April 10, 2016

### Determinism categories in Mercury

When you define a predicate in Mercury, you have to specify if it can fail or succeed more than once. This is called a determinism category.

The category is specified as part of a predicate (or function) declaration. For example:

``````:- pred get_partitions(
list(int)::in,
list(list(int))::out) is multi.``````

The `is multi` section says that this predicate belongs to the `multi` category.

The following tables describe the main determinism categories.

Maximum number of solutions:

Mode 1 > 1
det x
multi x
semidet x
nondet x

Failure:

Mode Can fail?
det no
multi no
semidet yes
nondet yes

(Based on information from https://mercurylang.org/information/doc-latest/mercury_ref/Determinism-categories.html#Determinism-categories ).

Other categories exist : `erroneous` , `failure`, `cc_mult` and `cc_nondet`. These are not discussed in this post, see the link above for more info.

Now a some of each category:

## det

These predicates in must always succeed . For example:

``````:- pred list_length(list(int)::in, int::out) is det.

list_length([_|R], Length) :-
list_length(R,SubListLength),
Length = SubListLength + 1.
list_length([], 0).``````

In this case this predicate is going to calculate the size of a list. It should not fail.

## semidet

These predicates can either succeed or fail. For example the following code shows the definition of a `first_even_number` predicate.

``````:- pred first_even_number(list(int)::in, int::out)
is semidet.

first_even_number([X|R], N) :-
(if (X mod  2) = 0 then
N = X
else
first_even_number(R,N)).``````

Notice that this predicate can fail for a couple of reasons:

• The input list may be empty
• The input list may not contain an even number

I think it's pretty nice that you these situations will be handled without explicitly writing code for it.

A use of this predicate looks like this:

``````...
(if first_even_number([3,41,5,32,342], EvenNumber) then
io.write_string("First even number: ", !IO),
io.write(EvenNumber, !IO)
else
io.write("Not even number found", !IO)
).``````

Another think that's pretty nice about Mercury is that, the compiler is going to detect inconsistent determinism annotations. For example, if I change the declaration of the predicate to:

``````:- pred first_even_number(list(int)::in, int::out)
is det.``````

The compiler is going to fail with the following error:

``````testsolutions.m:093: In `first_even_number'(in, out):
testsolutions.m:093:   error: determinism declaration not satisfied.
testsolutions.m:093:   Declared `det', inferred `semidet'.``````

## multi

The `multi` category is used for predicates that succeed in multiple ways. At least one solution exists.

For example the following predicate is used to get a pair of lists that, when concatenated together, result in the input list (ex. [1,2,3] result in { ,[2,3] }) .

``````:- pred partitions(list(int)::in,
{list(int), list(int)}::out) is multi.

partitions(InputList,Output) :-
(
Output = {[] ,  InputList}
;
InputList = [A|TMP],
partitions(TMP,{R,B}),
Output = { [A|R], B }
).``````

This predicate is `multi` because we can get several different pairs of lists that from an input list. For example:

``````main(!IO) :-
solutions(partitions([513,242,355,4]),Pairs1),
io.write(Pairs1,!IO),
io.nl(!IO).``````

Running this program result in the following output:

``[{[], [513, 242, 355, 4]}, {, [242, 355, 4]}, {[513, 242], [355, 4]}, {[513, 242, 355], }, {[513, 242, 355, 4], []}]``

In the case we use the `solutions/2` Mercury predicate to get a list from the generated solutions.

It's important to note that `multi` predicates must not fail.

## nondet

Finally the `nondet` category is used for predicates that result on 0 or many solutions.

For example the following predicate result on an even number that is part of the input list.

``````:- pred even_member(list(int)::in, int::out) is nondet.

even_member([X|_], X) :-
(X mod  2) = 0.
even_member([_|Rest], X) :-
even_member(Rest,X).``````

This predicate is `nondet` because :

• The list may be empty
• It may not contain an even number

Here's an example of how to use it:

``````main(!IO) :-
solutions(even_member([513,242,18,355,12,4]),Pairs1),
io.write(Pairs1,!IO).``````

Running this program result in the following output:

``[4, 12, 18, 242]``