Articles

Why nondeterminism is awesome

In Language design on June 19, 2010 by Matt Giuca Tagged: , ,

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:

:- pred p(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:

:- pred q(int::out) is nondet.
q(Y) :-
    p(X),         % Set X to the result of p
    Y = X + 1.    % Return X + 1

Now 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
:- pred tree_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 to map over each child, resulting in a set of sets of results. Then I have to power_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)
:- pred tree_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 values
def tree_processor(x):
    # Call another function to get a sequence of values
    for val in get_values(x):   # Sequence of solutions
        yield val

    # Recurse on the children of X
    for xchild in tree_child(x):    # Many children
        for val in tree_processor(xchild):
            yield val

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.

Advertisements

2 Responses to “Why nondeterminism is awesome”

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: