I’ve been using the Mercury programming language for several years for my PhD project. Now Mercury is a *functional logic* language (predominantly logic), which means instead of *functions*, it has *predicates*. Predicates are like subroutines (they have “output parameters” but don’t actually return values), but with an added power called “nondeterminism”. I’ll explain what that means shortly, but the point of this post is: I’ve never used it. I understand it fully but I’ve never used it in a real program because the opportunity never came up. I think a lot of people think it just adds complexity to the language with no real benefit. But the other day, I discovered how useful it can be.

Basically, nondeterminism means that a predicate can succeed multiple times, producing multiple results. The caller is largely unaware that the callee produced multiple results, as it isn’t returned as a “set” or “list”, it simply causes the caller to also produce multiple results. To give a quick example, say I have the nondeterministic predicate p:

:- predp(int::out)is nondet. p(X) :- ( X = 1 ; X = 2 ; X = 3 ).

This predicate succeeds three times, with the solutions {X = 1, X = 2 and X = 3}. Now when you call p, you don’t have to do anything special — you just automatically become nondeterministic too. So take predicate q:

:- predq(int::out)is nondet. q(Y) :- p(X), % Set X to the result of p Y = X + 1. % Return X + 1Now q just looks like regular code, but because p is nondeterministic, q also has three solutions: {Y = 2, Y = 3 and Y = 4}.

So what’s it all useful for?

Well in my compiler, I had a lot of code looking like this (only much more complex):

% A predicate that a tree, and returns a set of values:- predtree_processor(tree::in, set(val)::out)is det. tree_processor(X, Vals) :- % Call another predicate to get a set of values get_values(X, Vals1), % Recurse on the children of X and union all results together XChildren = tree_children(X), % Children as a set set.map(tree_processor, XChildren, Vals2Power), Vals2 = set.power_union(Vals2Power), % Union both sets together into the final set of results Vals = set.union_list([Vals1, Vals2]).This code is what I call “set-oriented”. Not only does this predicate deal with set objects all over the place, but the “get_values” and “tree_children” predicates must return a set, and any predicate which calls this code must accept a set.

There are a couple of problems with this code. Firstly, I need to number each of the sets “Vals1” and “Vals2” (the actual code had four sets). Secondly, note that I do a good deal of work in the recursion. The recursive call produces a set, but since I am recursing

over a set, I need tomapover each child, resulting in aset of setsof results. Then I have topower_union(flatten the set of sets into a set). This furious mapping and unioning is a hallmark of set-oriented code and it was steadily spreading throughout my code.Then I realised: This is what nondeterminism is for. The properties of my code (here and in several other places) were:

- A predicate which produces a set of values as a result,
- The final set is a union of a number of separately derived sets (Vals1, Vals2),
- The predicate deals with other sets of values,
- When dealing with a set of values, it produces results for each value in the set, independently (it
*maps*over the set, doesn’t*fold*).

What this means is, I could convert this and other predicates to nondeterminism to save a lot of complexity, making the code shorter and easier to read (assuming the reader understands nondeterminism):

% A predicate that takes a tree, and returns single value (with multiple solutions):- predtree_processor(tree::in, val::out)is nondet. tree_processor(X, Val) :- ( % Call another predicate to get a set of values get_values(X, Val) % Many solutions ; % Recurse on the children of X tree_child(X, XChild), % Many children tree_processor(XChild, Val) % Many solutions ).

Look what I’ve got now:

- Just one name for all of the results (“Val”).
- Cleanly separated (via the “;” disjunction operator) the distinct computations of the result set (which were previously bound to Vals1 and Vals2).
- No calls to map or union. Once a value is bound nondeterministically (such as XChild), it automatically “maps” all subsequent code. And the resulting set is automatically a “union” of every binding of Val.
- A nice declarative reading: “tree_processor(X, Val) succeeds if Val is a ‘get_values’ of X (whatever that means),
**or**if XChild is any child of X,**and**tree_processor(XChild, Val) succeeds.”

I did have to convert all the functions to nondeterminism at once, but I can stop at any level. It is fairly easy to convert back and forth between “sets of values” and “nondeterminism” (use **solutions.solutions_set** to convert a nondeterministic predicate’s results into a set; use **set.member** to convert a set into nondeterministic results).

So hey, this turned out to be quite a useful pattern, and it’s only possible in a logic language such as Prolog or Mercury.

## In other languages

Haskell allows a similar nondeterministic style, perhaps surprisingly, via the list data type (treating it as a monad), but that’s a completely separate topic. As ever, it’s really clean if you can wrap your head around monads.

Python’s generators offer something like nondeterminism. It sort of gives you *half* the features — it is easy to *produce* results in nondeterministic style, but not to *consume* them. To explain, using the example above:

# A function that takes a tree, and yields a sequence of valuesdeftree_processor(x): # Call another function to get a sequence of valuesforvalinget_values(x): # Sequence of solutionsyieldval # Recurse on the children of Xforxchildintree_child(x): # Many childrenforvalintree_processor(xchild):yieldval

This has the advantage of not having to produce sets (vals1 and vals2) and union them. However, unlike nondeterminism, calling a generator doesn’t automatically cause the rest of the caller to map over the generator’s results — you have to explicitly map or for-loop over the results. As a language designer, I wonder if there is a middle-ground — some generator-like mechanism which *does* automatically map over the results but which doesn’t take me all the way to a logic language.

Also note that while nondeterminism in Prolog/Mercury represents a *set* of results, in Haskell and Python it represents a *sequence* as the results come out in a definitive order.

Sounds a bit like array programming – I first encountered this in F-Script, and thought it was pretty neat: http://en.wikipedia.org/wiki/Array_programming

Yes, but in array programming, aren’t your variables explicitly arrays, except that arrays feature operations which work element-wise (a bit like if Python lists overloaded “+” not to concatenate, but to pair-wise add each element).

I’m not sure if that’s more flexible or less flexible. With nondeterminism, those variables aren’t “more featureful arrays”, they’re actually the types of the elements themselves. In some sense you can think of the predicate being like the “generator” section of a list comprehension — the result is always the cartesian product (permutations) of all elements of all “set assignments”.

For another thing, in array programming (correct me if I’m wrong), you would still need to do the final union of Vals1 and Vals2. Interestingly, as I said the Python generators solve half the problem (they can produce nondeterminism but not naturally consume it), it seems like array programming solves the other half (they can naturally consume nondeterminism but not produce it). So maybe the answer is to combine array programming with generators.