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

Complete code on codepad, showing output.

Other works in this space:

• Amb has been done in Ruby using their callcc operator
• Oleg lists a number of sources regarding the relationship between generators and non-determinism.
• Also in the category of generator hacks, C# async using iterators, before the async/await keywords were added. “.ExecuteAndWait()” serves a similar role as my “@nondet” decorator.
• Since I’ve gone this far, I might as well mention Beazley’s “A Curious Course on Coroutines and Concurrency” which covers some other crazy uses of generators.
• Generators are almost continuations, and continuations are the mother of all monads, which is why this sort-of works at all in the first place 🙂