# Non-determinism from generators

UPDATE(7/3/2013) I’ve found an earlier use of this technique written about on a blog, Valued Lessons – Monads in Python from 2008. Please read it too!

~~~

I was tinkering a bit tonight with simulating nondeterminism a-la McCarthy’s Amb operator — in Python. This is peculiar as Amb is usually implemented using either first class continuations or syntactic abstractions. Python supports neither.

So what is non-deterministic programming?

Background

In John McCarthy’s well known paper from 1960, he makes mention of programming using a hypothetical nondeterministic choice operator. Where a normal (deterministic) computer must always make definite choices at each step of computation, a non-deterministic computer is allowed to defer making a choice an explore both options, as if by making one choice in one universe and a different choice in a parallel universe. In some ways, this parallels the many-worlds interpretation of quantum mechanics.

In any case, a non-deterministic program can produce multiple outputs, or possibly no outputs. To express this, the ‘amb’ operator takes a list of zero or more arguments, and then arbitrarily picks one of the values to be the sole return value. If we say

``````x = amb(1, 2)
print x
``````

Then in one parallel universe, the value 1 is printed to console, while in another you instead see ‘2’ printed.

Finally, one can express termination as `amb()` taking no arguments, which effectively “implodes” that alternate universe, so only the other universes remain. This is used (in)effectively in Quantum Bogosort to sort in O(n) time per universe (with O(n!) universes).

``````def quantum_bogosort(thelist):
onelist = amb(*itertools.permutations(thelist))
if not is_sorted(onelist):
amb()
return onelist
``````

Ok, that code wasn’t real; it doesn’t work.

Working Code

A common beginners problem involves finding pythagorean triplets with amb instead of explicit search. Unfortunately, we can’t write amb in python. Fortunately, we can yield.

``````@nondet
def pythag (Return, amax, bmax,cmax):
a = yield range(1, amax+1)
b = yield range(a, bmax+1)
c = yield range(b, cmax+1)
if a*a + b*b == c*c:
Return((a,b,c))
``````

Try not to mind the `Return` variable too much. We’re using yielding for something else, so this extra parameter acts as a “return” operator. It’s in fact just another function.

The `@nondet` decorator wraps the user function with one that will progressively backtrack. The first time `yield range(1,amax+1)` is invoked, the `@nondet` decorator will immediately send the first element of that list. Eventually, Return will be invoked or control will leave the function, in which case, `@nondet` will start the function over again, save this time that first yield will return 2, and so forth.

The `@nondet` decorator is a thin wrapper around a pump routine. It creates an array to gather results into, and decorates the user function:

``````def nondet (fn):
def replacement (*args):
c = []
def Return (x):
c.append(x)
raise StopIteration()
nondet_pump(lambda:fn(Return, *args))
return c

replacement.__name__ = fn.__name__ + "_unyield"
return replacement
``````

The heart of non-determinism is found in this pump:

``````def nondet_pump (initiator, prefix=[]):
it = initiator()
xs = it.next()
try:
for p in prefix:
xs = it.send(p)
for x in xs:
nondet_pump(initiator, prefix+[x])
except StopIteration:
pass
``````

The `initiator` parameter is a curried wrapper around the user’s function. Each time pump is invoked, it will begin iteration, play back values (as results from ‘yield’) into the user’s function until it gets to the next yield. Then, for each list that the user yielded to `nondet`, another nested pump is started.

If the yielded list was empty, or if the user’s generator finishes iterating, we’ll escape out of this function normally, allowing the parent pump to move on to the next element for the particular yield it is servicing.

All this overhead comes at a price:

``````c0 = time.clock()
for triple in pythag(20,20,20):
print triple
c1 = time.clock()
print "elapsed time: %s seconds"%(c1-c0)
``````

Thankfully for us, modern computers are fast. On my computer, I get the results back instantaneously.

``````\$ python nondet_example.py
(3, 4, 5)
(5, 12, 13)
(6, 8, 10)
(8, 15, 17)
(9, 12, 15)
(12, 16, 20)
elapsed time: 0.010161 seconds
``````

Other works in this space:

## Join the Conversation

1. 2. 3. 4 Comments

1. patrick says:

What if the choice is made in another function but rated in blub?

def selc():
yield range(1,21)

@nondet
def blub(Return):
c=selc()
if c>5:
Return(c)

How to achieve this?

1. aaron says:

It’s local to functions annotated @nondet, but you could annodate selc as well. Then you could say

```@nondet def selc(Return): r = yield range(1,21) Return(r) @nondet def blub(Return): c = yield selc() if c > 5: Return(c) ```

Then, blub() returns the sequence 6 thru 20.

2. patrick says:

Thank you, I should have seen that 🙂

Your solution is very elegant, no comparison to the strange instances of amb-operators created for Python by others.

With this it should be very easy to convert arbitrary randomized algorithms to systematically searching ones. Normally I used Prolog for nondeterminism and I was always wondering why this mighty concept never found its way to languages of different paradigm.

Leave a comment